Possible Issues With the P != NP Proof 147
An anonymous reader writes "We previously discussed news that Vinay Deolalikar, a Principal Research Scientist at HP Labs, wrote a paper that claimed to prove P is not equal to NP. Dick Lipton, a Professor of Computer Science at Georgia Tech, analyzed the idea of the proof on his blog. In a recent post, he explains that there have been many serious objections raised about the proof. The post summarizes the issues that need to be answered in any subsequent development, and additional concerns are raised in the comment section."
What? (Score:1, Interesting)
Current Status (Score:5, Informative)
The original discussion was in a Google Doc but has since moved to a wiki [michaelnielsen.org].
Info: Previous post explaining the proof more clearly [wordpress.com]
Paper [hp.com] (not wort reading for most of us)
Re:Current Status (Score:5, Funny)
Minor typos like a ! that m,ade it into the paper by accident.
Mathematicians are gathering to vet this paper (Score:5, Informative)
For anyone interested in the details, you can find a lot more on this wiki [michaelnielsen.org], where a lot of mathematicians are weighing in on the proof and its potential flaws. Mathematicians are gathering from all over to examine this paper because it's so interesting. Even if one of the serious objections that have been raised so far kills it, it contains some novel ideas that will get people thinking.
They've also been gathering the news coverage and such, so it's probably the best place to find up-to-date information about this proof. It seems to have sparked quite a lot of interest for a paper that hasn't even been properly published.
Re: (Score:2)
If there is a problem but someone else solves it, who gets the prize?
Re: (Score:2)
Re: (Score:1, Insightful)
Indeed.
Irregardless of whether he's correct or not, the fact that he came out and made it public to be vetted is quite ballsy. Further, the discussion it generates *cannot* be a negative thing.
Kudos to Vinay Deolalikar. You've brought about a minor storm that will bring about positive results.
Free vocabulary lesson. (Score:2, Informative)
Irregardless is not a valid word.
Publication Bias (Score:5, Funny)
Re:Publication Bias (Score:5, Funny)
Re: (Score:1, Troll)
P=NP is a question in computer science, not mathematics. The two fields split about 50 years ago.
Re: (Score:2)
P=NP is a question in computer science, not mathematics. The two fields split about 50 years ago.
But computer science is mathematics, or rather a subset thereof.
Re: (Score:1, Troll)
But computer science is mathematics, or rather a subset thereof.
No, it's not. The relationship between computer science and mathematics is similar to the relationship between physics and mathematics: there is some overlap, lots of fruitful cooperation, and some fundamental differences in methodology and subject matter.
Even if computer science were a subset, it's only the computer scientists that are gathering to vet this paper. Saying "mathematicians are gathering to vet this paper" would be as misleading
Re:Mathematicians are gathering to vet this paper (Score:5, Insightful)
>No, it's not. The relationship between computer science and mathematics is similar to the relationship between physics and mathematics:
No it's not the one IS the other and it's the perceived DIFFERENCE that doesn't exist. It's purely a perception -and a DELIBERATE illusion at that, designed to simplify the process. Ultimately it's easilly provable that every computer program is a simple mathematical function - so simple in fact that it is in fact a single number.
There is nothing weird about this- if you know lambda calculus, godel-number and Turing machines it's simple logic. We have never done anything to "split" the fields. All computer science did was to create a (very shallow) layer of pretense through which ot access the maths.
To suggest it is anything OTHER than mathematics is to prove you have absolutely no idea how computers actually work. In the real world- every computer is a universal turing machine.
If you have any real doubt - just consider this: any program COULD be written in lisp.
Lisp is DIRECTLY based on lambda-calculus - in fact the ONLY (minor) difference as small syntactical changes designed to make it easier to TYPE lambda on a computer (it was after-all designed for writing in).
Lamba-calculus is a simple form of mathematical language - like algebra or godel numbers or any of a dozen other ways to write down 2+2=4 that are all just different ways of expressing it designed to be useful for different purposes.
It's true that currently the most popular languages do not follow the lisp "look like the function you are" structure -but this is because in single-CPU machines top-down programs were slightly more similar to how the hardware actually PROCESSED the functions - and that made it easier to program in.
Expect this to change in the next few years - multi-CPU machines are actually EASIER to program for in a functional language like lisp - which makes all those nasty multithreading issues just go away by putting you on the actual mathematics that happens.
Re: (Score:1)
Re: (Score:3, Funny)
CS is a subset of biology. Any question in CS can and must be restated in a human brain...
Re: (Score:2)
To suggest it is anything OTHER than mathematics is to prove you have absolutely no idea how computers actually work. In the real world- every computer is a universal turing machine.
If you have any real doubt - just consider this: any program COULD be written in lisp.
Lisp is DIRECTLY based on lambda-calculus - in fact the ONLY (minor) difference as small syntactical changes designed to make it easier to TYPE lambda on a computer (it was after-all designed for writing in).
That may satisfy the folks who can o
Assembly language is typeless (Score:2)
the mathematical operations that comprise a function is the function it is, and nothing looks more like that than the underlying assembly.
Assembly language doesn't have a notion of types. For example, the Python expression [x + 5 for x in some_list] starts with a list (or other iterable item) and ends with a list. Assembly language has to explicitly loop over the elements, apply the operation, write back the result, and hope the rest of the program treats it as a list.
Re: (Score:1)
Assembly language doesn't have a notion of types. For example, the Python expression [x + 5 for x in some_list] starts with a list (or other iterable item) and ends with a list. Assembly language has to explicitly loop over the elements, apply the operation, write back the result, and hope the rest of the program treats it as a list.
Or, in assembly, you could implement functions which verify the type of parameters and branch to exception code if they don't match. Which is exactly what Python is doing unde
Re: (Score:2)
everything a computer does is just math and can be translated into any equivalent math and you'll get the same result
Being able to simulate and model something at a low level doesn't give you a high level understanding. A mathematician understands boolean logic, but that doesn't mean he has the knowledge and skills to design a CPU or program it. That knowledge and those skills aren't taught in mathematics, they are taught in computer science.
Re: (Score:2)
Being able to simulate and model something at a low level doesn't give you a high level understanding. A mathematician understands boolean logic, but that doesn't mean he has the knowledge and skills to design a CPU or program it. That knowledge and those skills aren't taught in mathematics, they are taught in computer science.
Yes, you are completely correct to say that the specific disciplines necessary to write computer programs, or to design a CPU (which is a combination of computer science and electrica
Re: (Score:2)
Is math and is covered by mathematics degree programs are completely orthogonal properties.
Nevetheless, it is computer scientists, not mathematicians, that are gathering to to vet this paper: if you work on the theory of computation, you are a computer scientist, no matter what your training, background, or methods.
Re: (Score:2)
>. A mathematician understands boolean logic, but that doesn't mean he has the knowledge and skills to design a CPU or program it. That knowledge and those skills aren't taught in mathematics, they are taught in computer science.
This is a half-truth at best. Firstly because the knowledge to design a CPU isn't taught in computer science either - it's taught in electronic engineering. The real problem is that so few people today actually studied computer science - learning programming != computer science.
Re: (Score:2)
learning programming != computer science
Correct: learning to program is a strict subset of computer science. (CPU and VLSI design may or may not have branched off from computer science now, that's debatable.)
There's a REASON that most of the algorithms we use every day were originally designed by people like Donald Knuth - who are professional MATHEMATICIANS.
Donald Knuth was trained as a mathematician before computer science existed, but today he is a computer scientists at the computer science department.
Re: (Score:2)
>Donald Knuth was trained as a mathematician before computer science existed, but today he is a computer scientists at the computer science department. Go check his home page.
You know there are OTHER specialized subfields of mathematics - and Knuth is among the primary people standing behind the belief that computer science is maths - and has testified in the supreme court his belief that it is such pure maths that it should be unpatentable.
>Be that as it may, it's computer scientists, not mathematici
Re: (Score:2)
Speaking as a total non-mathematician here...
To suggest it is anything OTHER than mathematics is to prove you have absolutely no idea how computers actually work. In the real world- every computer is a universal turing machine.
If you have any real doubt - just consider this: any program COULD be written in lisp.
Lisp is DIRECTLY based on lambda-calculus - in fact the ONLY (minor) difference as small syntactical changes designed to make it easier to TYPE lambda on a computer (it was after-all designed for writing in).
Lamba-calculus is a simple form of mathematical language - like algebra or godel numbers or any of a dozen other ways to write down 2+2=4 that are all just different ways of expressing it designed to be useful for different purposes.
OK fine, but if untyped lambda calculus is a form of notation that's useful for describing computation, isn't this a circular argument? It's a computer. Of course a form of notation used to express computation would be able to describe what it does.
If, on the other hand, I want to describe a system where I have a bunch of rocks in one pile, and I move rocks to another pile based on certain logical criteria, forming a kind of "loop" ... couldn't that also be expre
Perfect mathematical model of a computer (Score:2)
You can call it math if you want, but if I can write a program to do what I want to do, it makes no difference to me if it's math or not.
The difference is that a computer can be perfectly modeled by math because all operations on a computer are mathematical. Your example of moving a rock include incompletely modeled physical fields such as robotics (how to move the limb that moves the rocks) and computer vision (how to determine where to place the rocks so that they don't fall).
Re: (Score:2)
So in the end, your comments sound like the same kind of navel-gazing that says "math is everywhere" .... "Look, Bobby, see the Golden Ratio in the structure of this leaf? Math is everywhere!" "No dad, that is not math. That is a leaf. Math is how you think about the leaf."
Right. The leaf can be described by math. Math is the description, an abstract representation of the concept of how the leaf is structured.
A computer program is nothing more than an abstract representation of mathematical operations. "
Re: (Score:2)
>OK fine, but if untyped lambda calculus is a form of notation that's useful for describing computation, isn't this a circular argument?
In a sense being circular makes it true - because you can translate between a form of pure maths, and a computer language that's a "circle" - the fact that the meaning remains utterly unchanged throughout the circle means they are identical.
>It's a computer. Of course a form of notation used to express computation would be able to describe what it does.
You think that'
Re: (Score:2)
If I write 2+2=4 on a piece of paper, is the pattern of graphite math or is the math a pure idea in my mind (and the minds of those who read it)?
Ooh, Platonic Realism!
Re: (Score:3, Informative)
You don't REALLY need to CAPITALIZE words so FREQUENTLY to make your point.
Re: (Score:2)
Cool... and since most porn is digital now, and displayed on computers, can we then say that porn is just a calculation in lambda calculus?
Who knew that watching porn was the equivalent of doing calculus!!!
Re: (Score:2)
more like watching a machine perform pre-constructed calculus. But hey, who's keeping score? Fap away.
Re: (Score:2)
Cool... and since most porn is digital now, and displayed on computers, can we then say that porn is just a calculation in lambda calculus?
I'm sure I don't need to explain the difference between an algorithm and a dataset.
Re: (Score:3, Insightful)
Ultimately it's easilly provable that every computer program is a simple mathematical function - so simple in fact that it is in fact a single number.
Every biological system is a physical system, but if you study physics, you'll know next to nothing about biology.
All computer science did was to create a (very shallow) layer of pretense through which ot access the maths.
There is no "pretense". Theoretical computer science is a highly mathematical discipline, but it deals with issues that are of no interest
Re: (Score:2)
>>Ultimately it's easilly provable that every computer program is a simple mathematical function - so simple in fact that it is in fact a single number.
>Every biological system is a physical system, but if you study physics, you'll know next to nothing about biology.
If you do the quantum wave functions for every particle in the cat, in the milk, in the floor... you can predict that the cat will drink the milk. It's in there - though granted with current technology it would take us longer than the e
Re: (Score:2)
Re: (Score:2)
All those things existed before mathematics, were not created by mathematicians, and exist independently of whether mathematics did or not.
We use mathematics to describe them but they all predate it.
Computer science doesn't share ANY of those traits. It did not, indeed COULD NOT exist before mathematics, it was created BY mathematicians and it cannot exist indepently of mathematics.
That's why it is in fact wrong to claim that it's APPLIED mathematics (though it's useful to think that way) - it isn't, it IS
Re: (Score:2)
Re: (Score:2)
Mathematics is a model for how the universe works
Uh, no its not. Mathematics is *used* to model how the universe works, but it's not, itself, a model.
Re: (Score:3, Funny)
Strictly speaking, every computer in the real world is a finite state machine that's complex enough to simulate a universal Turing machine. It's a subtle difference that really only matters if you're considering the math behind it ;)
Oh Snap!!
Bounded tape makes a computer an LBA (Score:2)
Strictly speaking, every computer in the real world is a finite state machine that's complex enough to simulate a universal Turing machine.
Not exactly. A finite state machine cannot represent the unbounded tape of a universal Turing machine. I prefer to model computers as deterministic linear bounded automata [wikipedia.org], which are identical to Turing machines except that they cannot advance the index past the end of the input. Each LBA has an equivalent FSM, but unlike an FSM, an LBA has an index, which allows reasoning about arrays and pointers.
Re: (Score:2)
Actually, it doesn't. Educational programs might include/require them, but that's not the same thing (or if it is, Spanish Language and Ancient World Mythology are also CS).
Re: (Score:1)
Re: (Score:2)
writing a Lisp interpreter (or compiler) that can use multiple CPUs effectively is no small task.
Just making a thread-map counterpart to the map functions [delorie.com] will help use more CPUs: break the list into portions, have each thread process one, and slam them back together. This might be easier on splittable list structures, such as skip lists [wikipedia.org] or array lists [wikipedia.org], than on the common linked list.
This and... (Score:1)
buffer overflow exploits, quantum physics, the pre-big bang universe and phone company math make my head hurt. Understanding this sort of thing must be like having a set of truck nuts hanging from your geek card.
Re: (Score:2)
Those are all very different things that require very different skills and interests.
Field: Computers.
Geek score: 1
Re: (Score:2)
I for one (Score:5, Funny)
Re: (Score:1, Funny)
It's not that hard, just try to stay with me...
P != NP
NP has an N in it
So it's not the same as P
P != NP
QEDuh!
If you need any help with any other math stuff, just let me know.
Re: (Score:1)
It's not that hard; try to stay with me:
P != NP
NP has an N in it
So it's not the same as P
P != NP
QEDuh!
If you need any help with any other math stuff, just let me know.
Re: (Score:3, Insightful)
NP has an N in it
So it's not the same as P
Prove it.
Re: (Score:1)
Stupid and ignorant are not the same thing. Confusing them is a common geek fallacy.
Re: (Score:2)
No no, I'm pretty sure he means stupid.
I feel the same way, but I pretend like I'm just ignorant when I read it. Makes me feel better. ;)
Hard core (Score:5, Interesting)
I have tremendous respect for the folks who continue to "dabble" in this stuff. I'm sure that for their efforts they have been rewarded with glimpses of indescribably beautiful works of both man and of nature.
Re:Hard core (Score:5, Funny)
How cool was that, I assume it was to give you a theoretical basis for the use of car analogies.
Re: (Score:2)
How cool was that, I assume it was to give you a theoretical basis for the use of car analogies.
More likely they were thrown on a bike in the midst of the Tour de France w/o the helmet.
Re: (Score:1)
It looks like (Score:2, Insightful)
Vinay Deolalikar was a little unfortunate in that his unreviewed theory got more attention than he believed it would. It seems his paper offers a new approach, but as it was a first draft had a number of holes and was by no means ready for "prime time".
On the other hand, you could say that broadcasting that you have a solution to one of the most famous remaining unsolved problems was a little ill-advised.
Re:It looks like (Score:4, Insightful)
I read that he intended his proof only to be distributed to a select group of people to help him review it. Then it got away, bits being infinitely copiable.
If someone else released his proof into the wild, we can hardly blame him.
--PM
Re: (Score:2)
I think he knew exactly how much attention his paper would get.
What he probably didn't know is that were disturbing flaws within it.
Even so, he was humble enough to RFC instead of just publishing it.
Okay honestly ... (Score:2)
I don't buy that nearly as many people on here understood that as are going to post on here acting like they understood that.
Hopefully one of Slashdot's crack editors will repost a lighter story this morning to comment on ...
Dick Lipton (Score:4, Informative)
Re: (Score:2)
And he has a funny name in the proud tradition of Lipschitz.
Re: (Score:2)
He also knows a lot about tea, and decided he makes more money by selling the shitty kind.
Re: (Score:2)
He also knows a lot about tea, and decided he makes more money by selling the shitty kind.
Cheap/easy to use. Universal appeal.
Re: (Score:1)
What would be better? (Score:4, Interesting)
In one case encryption can be proven secure, in the other we loose encryption but gain efficiency. What would be better for humanity going forward, being able to solve box packing problems instantly or having nearly perfectly secure communication?
Re: (Score:3)
We can do cryptography without relying on P!=NP. That's going to be longer to initialize but that would probably work.
Re: (Score:3)
Problem solving (Score:3, Interesting)
Can the proof be verified in polynomial time?
I'm one of those ex-mathamaticians who still sulks at the existence of discussions beyond my ability to comprehend, where there is absolutely nothing constructive I can add. As a student back in the day, I was always nervous of proofs that were longer than a page - it always seemed to me that once a single proof got beyond a certain length, there was always some lingering doubt that some flaw or special condition had been overlooked, doubt that would pass on to every result that then used it. I guess that's the difference between learning math (where the problems are deliberately selected by textbook authors to have nicely bounded complexity) and researching math (where nobody knows how many twists and turns there are in the road between you and your goal).
Re: (Score:2)
From my virtually non-existent understanding of this problem, it sounds like issues surrounding polynomial time are where the bulk, if not all, of the issues raised about the proof lie.
Well, duh... (Score:1)
The paper may target the wrong hardness phase of randomized {k}-SAT.
A Layman's Take (Score:1)
I am a layman (not a mathematician) however there are several large points of suspicion that I can identify with this proof. First of all, its 102 pages long. Second of all, its a proof by contradiction, namely that certain known statistical behaviors of a formula are contradicted for the author's constructions if P=NP. So in reality, a proof like this requires not only examination of the particular proof in question, but of all other theorems and inferences that are relied upon to construct the contradi
Scott Aaronson's take (Score:2)
Note this is from a respected MIT prof: [scottaaronson.com]
My hunch is he's pretty sure it's broken.
Incompleteness (Score:5, Interesting)
Yes there can be a proof to prove that there is no proof. Check out Godel's Incompleteness Theorem
http://en.wikipedia.org/wiki/G%C3%B6del's_incompleteness_theorems [wikipedia.org]
Gödel's incompleteness theorems are two theorems of mathematical logic that establish inherent limitations of all but the most trivial axiomatic systems for mathematics. The theorems, proven by Kurt Gödel in 1931, are important both in mathematical logic and in the philosophy of mathematics. The two results are widely interpreted as showing that Hilbert's program to find a complete and consistent set of axioms for all of mathematics is impossible, thus giving a negative answer to Hilbert's second problem.
Not sure if any such effort exists though in this case.
Yes, they've tried that (Score:5, Informative)
They've tried that, but all that's been proven so far is that several types of proof won't work, rather than proving that it's impossible to prove. The first few sections of this paper itself go into detail about why this proof isn't one of the kinds of proof that won't work, incidentally.
Terrence Tao has a blog post on why a P=NP proof can't be relativisable [wordpress.com] if you're interested. Incidentally, there are several other classes of proof that won't separate P from NP.
Re:Yes, they've tried that (Score:5, Funny)
Re: (Score:1)
This deserves +5 funny if any comment on this thread does.
Re: (Score:2)
I have discovered a truly marvelous proof that P != NP, but this comment is not rated highly enough to contain it.
Re: (Score:2)
Oh for mod points. That was brilliant.
Re: (Score:1, Interesting)
Here's a proof short enough to reproduce in a comment. http://www.win.tue.nl/~gwoegi/P-versus-NP/argall.txt [win.tue.nl]
P=NP - An impossible question
A proposed proof of undecidability by Nicholas Argall, 25 March, 2003.
There has been much debate surrounding answers to the question of P=NP.
The problem is that we cannot answer the question until we have successfully
asked the question. The question is impossible to ask, that it why it will
never be answered.
1) A provable answer to the question P=NP requires a complete and consistent
formal statement of the question.
Rationale: Hopefully, this is self-evident. It is certainly axiomatic that
a formally provable statement be expressed in formal terms. Completion and
consistency follow from the requirement to provide a proof that is not
subject to challenge.
2) A complete and consistent formal statement of the question must
incorporate a complete and consistent formal definition of the sets P and NP
Rationale: Hopefully, this is also self-evident. (I have left out the
requirement to define the equality operator, since it is defined for us by
set theory.)
3) A definition based on a potentially undetectable characteristic is
incomplete
Rationale: We cannot accept the definition of the set NP purely in terms of
its members having a property (a solution test in polynomial time) that we
have no reliable mechanism to detect. Therefore, a complete definition of
the set NP must be arrived at via some other means.
4) The only possibility for a complete definition of the set NP is a
language
Rationale: Once we rule out observation of characteristics, our only means
towards a definition of the set NP is to formulate a language, a procedure
for testing the formal expression of the candidate problem that will accept
the problem or reject it.
5) No formal language capable of expressing non-trivial mathematical
problems can be consistent and complete
Rationale: As proven by Godel.
6) Therefore, no consistent and complete definition of the set NP is possible
Rationale: If we accept that the set NP can only be rigorously defined via a
language, this conclusion follows from the premises above.
7) Therefore, no consistent and complete statement of the problem of P=NP is
possible
Comment: A conclusion which is not only proven in this paper, but supported
by the years of argument between mathematicians regarding the relevance of
proposed answers to the problem.
8) Therefore, P=NP is undecidable
Comment: Given our inability to ask, we are unable to answer.
Re:Incompleteness (Score:5, Insightful)
Re: (Score:1)
Re:How? (Score:5, Informative)
Re: (Score:1)
In the Incompleteness Theorem, a system of axioms is complete if, for all statements in the system, either the statement or its negation is provable from the axioms. A system is consistant if there exist no statements for which both the statement and its negation are provable.
Basically, his "proof" is "Hey, we don't want a contradictory or unfinished definition, right? And those words mean the same thing as consistant and compl
Re: (Score:2)
Re: (Score:2)
That there is a problem should be evident from the fact that this proof doesn't use any specifics of P=NP, so it can be used to prove anything undecidable, which is clearly wrong, since there exist proven theorems.
Re: (Score:2)
3) sounds very much like the objections of early mathematicians when they had to deal with prime numbers. "there isn't a function that generates all the possible primes, so how can we work with them?"
Re: (Score:2)
How could P=NP be proven undecidable? If P=NP is proven undecidable, it means there can be no deterministic polynomial-time algorithm to solve an NP-complete problem in polynomial time (because such an algorithm would prove that P=NP). If no such algorithm exists, then P!=NP.
(this doesn't mean P=NP can't be undecidable... it just means that if if it is undecidable, the question of its undecidability is also so, and so on up the line)
Re: (Score:3)
If, in step 2, you mean a formal decision procedure to tell if an problem is in P or in NP, no, we don't. We know that any problem in P is also in NP, by definition. Therefore, if we can prove that any problem in NP is also in P, using only properties we've proved belong to NP, we've got a proof. If we can prove that any individual problem in NP is not in P, we have a proof of the opposite. Neither of these requires a general NP- or P-detector.
Technically, we could possibly have a proof one way or an
Re: (Score:1)
I almost modded you interesting, but I can't.
I don't have enough of a background to realize if, for the particular issue of P (!)= NP, it makes sense to think of decidability. I do suspect it doesn't, because the problem is pretty old, and I've never heard of anyone talking about its decidability.
When there's a million dollars involved, I've learned to expect that enough people tried enough different ways to exhaust all the ideas I can have in 5 minutes from hearing about the problem (and ever since I've he
Re: (Score:2)
(I am not a mathematician)
If a proof that P=NP is undecidable exists then P=NP is decidable.
If P=NP then there is a polynomial time reduction from a P problem to an NP complete problem. That algorithm is sufficient to prove that P=NP.
If P=NP is undecidable then no such algorithm can exist and therefore P!=NP.
Therefore a proof that P=NP is undecidable is sufficient to prove that P!=NP and therefore P!=NP cannot be proven to be undecidable.
(The only loophole I can see is that the algorithm could exist but cou
Re: (Score:2)
I am not sure in what sense you use the term "undecidable", but if (as it seems likely) you used it to mean independent [wikipedia.org], then your argument fails at steps 2 and 3.
A proof that P =? NP is undecidable has to only show that one can neither prove nor disprove this statement: it need not show that no polynomial-time
Re:Proof that a proof can't exist? (Score:4, Informative)
This question has been considered by quite a few different people; search google for P vs NP independent [google.com] ("independent" meaning independent from the usual accepted axioms for mathematics, i.e., can't be proven using the currently accepted axioms).
There's a nice survey paper about this question that's very readable if you're willing to invest some time: Is P Versus NP Formally Independent? [scottaaronson.com].
Re:Proof that a proof can't exist? (Score:4, Insightful)
Not really. It's proof of a negative which is vastly more difficult than a positive. For example, proving no dogs can have black spots is much harder than dogs can have black spots. You'd have to prove how it's impossible for any dog in existence to get black spots. The opposite only requires existence of 1 dog with black spots.
It's the same with Fermat's Last Theorem: Prove no solutions exist for x^n+y^n=z^n for all integers x,y,z where n is an integer greater than 2. That proof takes hundreds of pages.
Re: (Score:2)
Re: (Score:3, Interesting)
How about this simplification:
P is the class of problems for which you can get the answer (output) quickly (i.e. in polytime).
NP is the class of problems for which you can verify an answer quickly.
P = NP is the question of whether all problems where you can verify the answer quickly have corresponding solvers that also find the answer quickly. If yes, P = NP, if not, P != NP. It's really a question about how powerful algorithms can be - and thus how powerful intelligence can be, because if P = NP, you could
Re: (Score:1, Interesting)
Thank you.
Also, thinking of that just blew my mind. Now I hope that P == NP would really be true because of all the possibilities...
Re: (Score:3, Funny)