Many people want to know if there are any NP problems that are not P Problems.
That means they would like to know if there are any problems where the answer
is hard to find, but if someone says he has the answer, it is easy to check
if that answer is correct.
This is probably the core of the article, but I find it misleading. The truth is that we need to either prove that the answer to a certain problem will always be hard to find (hence proving that P =/= NP) or we need to prove that all NP problems have in theory a P algorithm (P = NP). We currently have many NP (="easily" verifiable) problems that have no known solving algorithm in polynomial time. The evidence would so far suggest that P =/= NP, but this is empirical not mathematical. It's possible that all those non-P problems have some way to resolve them in P, but it doesn't look like it right now.
I would thus rephrase the core explanation as something like this:
"For problems where the correct answer can be checked easily, there are two possibilities: If (P = NP) is correct, that means there is always an easy way to come up with a solution no matter how complicated the problem is. If the opposite is correct (P =/= NP), there are some problems where the answer will always be difficult to find no matter how clever the solution is. We don't know yet which one of these possibilities is true."
the lack of a known polynomial time algorithm could be interpreted as evidence that P =/= NP, but it could just as easily be interpreted as evidence of our primitive state of knowledge with regard to algorithms. Suppose that P = NP, but the minimum complexity of any NP-Complete problem is O(n^(# of atoms in the universe)); we might never discover such a complicated algorithm, but that in no way implies it doesn't exist.
still, i see your point, but i think your phrasing is too complicated; i've changed it to this:
It is known that all P problems are NP problems; the proof
requires math which is too complicated for this article but
may be explained in the future. Many people want to know if
there are any NP problems that are not P Problems. That
means they would like to know if there are any problems
where the answer cannot easily be found by a computer, but
if someone says he has the answer, it is easy to use
a computer to check if that answer is correct.
Your idea about the the primitive state of our algorithm knowledge is interesting. This has nothing to do with the article, but I do believe there are deep philosophical implications here. If we knew (and could make use of the fact) that everything is P, it would fundamentally shift our relationship with reality. I would go so far as to say that P =/= NP is an instinctive model we have formed about the universe as it presents itself today. If this were to change, it would affect pretty much everything we're doing - I can't even begin to imagine what would happen on the day abstract problem solving becomes a P algorithm...
N^(1,000!!!!) is P but you need a rediculusly large number before 2^(N) is worse (N >= 2). Generally N^5 is about as far as you want before you can do anything with 3 digit numbers.
what happens in the example i gave above? if the minimum complexity of solving any np-complete problem is O(n^2e80) then we'd need such massively parallel computing that you'd have to turn pretty much every atom in the universe into a computing device.
i agree that p != np is the instinctive model most theoreticians have about the universe, but if science has taught us anything in the last 100 years, it's that our instincts are often wrong, and the story of science will probably never be finished.
Absolutely, but I'd say that the idea of brute-forcing the entire universe - while theoretically and mathematically sound - goes against the spirit of what we're trying to express with Big O. Solutions like these work in a theoretical universe with infinite matter and possibly over infinite time, but if the world is indeed finite (which it may very well be) any Big O expression containing the sum of all states of all atoms in the universe does contain a practical infinity.
i'm not sure what you mean by the 'spirit' of Big-O; i find the question fascinating because it is relatively easy to understand the concepts involved, yet it's been 40+ years since we understood enough to be able to ask the question, and we still don't know the answer. when you couple that with the fact that the prevailing wisdom that our inability to find an algorithm implies that it can't exist, the contrarian in me goes nuts: the academic attitude is always "we're so smart, if we can't find it, it must not exist," and i get a kick out of arguing for more humility on their part.
even though a polynomial-time algorithm with a massive polynomial would still be computationally intractable, even a proof that such an algorithm exists, but is too complicated to express using all the atoms in the universe as bits would probably open the doors to all kinds of proofs and techniques we cant' even imagine.
I would thus rephrase the core explanation as something like this:
"For problems where the correct answer can be checked easily, there are two possibilities: If (P = NP) is correct, that means there is always an easy way to come up with a solution no matter how complicated the problem is. If the opposite is correct (P =/= NP), there are some problems where the answer will always be difficult to find no matter how clever the solution is. We don't know yet which one of these possibilities is true."