Once you understand what PvsNP problem is actually all about, you might as well try and solve it.
In loose terms, the P vs. NP problem actually seeks an answer to this simply stated question:
"Is finding a solution to a math problem equally hard in comparison to verifying that it IS a solution ?"
Math guys usually "search" for a solution to their problem (e.g. solving some equation), but this can apply to "searching" any data set.
Imagine a program that searches for a solution to some equation. That program will most certainly consist of two major parts: a searching part (the solver) and a verifying part (the verifier). The solver tries to construct a solution by some rules and a verifier checks that it actually *is* a solution.
This solution constructing part is like when you do all sorts of manipulations (factoring, cancelling common terms, ...) to solve an equation, and this verifying part is more like when you plug in some values for your solution back to the original equation to check if both sides turn out equal.
The first part will usually take up much time, as finding a solution to some equations is sometimes hard, but once the right solution is constructed, the verifier will take only a fraction of that time to check if that actually IS a solution. The PvsNP asks if those two parts are actually the same thing, because it would be nice of course, that solving an equation is as easy as checking the result.
Another way to look at it, it's basically a question about searching trough (potentially large) sets of data. In that context the PvsNP asks this:
"Is there a systematic way of searching trough a large data set ?"
(a large data set means for example, a data set not completely searchable in the course of one persons lifetime, for example the whole Internet)
Of course, people have been trying to answer this for decades ever since the computer era started, but with no luck, in my opinion because of the way the final solution needs to be presented.
It is widely believed that P is not equal to NP, because otherwise it would have baffling implications for say cryptography and code breaking. As there is a huge number of potential passwords that one can make up, a positive answer to PvsNP means that a brute force search is not necessary when trying to guess someone's password and there is also a systematic way how to obtain it. On the other hand, if P is not equal to NP than it means that there is no such thing.
Also, in this digital age, when almost everything is stored on a computer (music, pictures, texts, ...) if P = NP is true then we could generate any piece of music, any picture, anything ... by means of a computer program that would solve P vs NP, we just "search" for it, provided we have a computer program that recognizes that something is "a piece of music".
Finally, the PvsNP can be restated in terms of creativity as: "Can creativity be effectively automated ?"
The hardest thing about solving the problem is actually proving that either case is true. There are of course up till now many false starts and dead ends, and people today that are still trying are trying to prove that in fact P does not equal NP. Richard Karp, one of the most renowned computer scientists once said that this problem will someday be solved (either way) by someone under thirty using a completely new method. So, until then, you might try and solve it for yourself.
What if it's only solvable as long as the solution is known to exist? Can't run a successful search for music that doesn't exist. I think the only factual solution would be (P=NP) as long as (P-NP>0).
- Badges
- Science topic
- Similar topics
- Mathematics