Complex matters for the millenium
August 8, 2010 11:57 PM Subscribe
I am pleased to announce a proof that P is not equal to NP. In this paper, Vinay Deolalikar (HP Labs) proposes a proof to answer the most important problem in its field of mathematics.
Academics stay cautious until the proof is scrutinized further by the community.
Academics stay cautious until the proof is scrutinized further by the community.
I think you'll find the most important, unanswered, problem in the field of mathematics is how 10 people can put in $20 each towards a $200 restaurant bill and there always be $10 missing when the cash gets counted.
posted by MuffinMan at 12:11 AM on August 9, 2010 [31 favorites]
posted by MuffinMan at 12:11 AM on August 9, 2010 [31 favorites]
It's hard to stress enough how important it would be if somebody actually proved this. On the other hand, everybody has been assuming that P is not equal to NP for decades now, so the algorithms that power what you do with computers probably won't be affected at all.
posted by twoleftfeet at 12:23 AM on August 9, 2010 [1 favorite]
posted by twoleftfeet at 12:23 AM on August 9, 2010 [1 favorite]
It's hard to stress enough how important it would be if somebody actually proved this.
Outside of the intellectual interest, why? Cryptography?
posted by phrontist at 12:26 AM on August 9, 2010
Outside of the intellectual interest, why? Cryptography?
posted by phrontist at 12:26 AM on August 9, 2010
The wikipedia article describes exactly how important this is
posted by Sparx at 12:37 AM on August 9, 2010
posted by Sparx at 12:37 AM on August 9, 2010
Yep. For starters:
The question of whether P equals NP is one of the most important open questions in theoretical computer science because of the wide implications of a solution.[2] If the answer is yes, many important problems can be shown to have more efficient solutions. These include various types of integer programming problems in operations research, many problems in logistics, protein structure prediction in biology,[4] and the ability to find formal proofs of pure mathematics theorems.[5] The P versus NP problem is one of the Millennium Prize Problems proposed by the Clay Mathematics Institute. There is a US$1,000,000 prize for resolving the problem.[6]posted by pracowity at 12:38 AM on August 9, 2010
Outside of the intellectual interest, why? Cryptography?
There's a whole class of interesting problems that have important real world applications for which no efficient algorithm is known. This would mean that no efficient algorithm exists. The most important consequence is that CS grad students can stop wasting time looking for efficient algorithms and get back to playing Starcraft.
posted by qxntpqbbbqxl at 12:39 AM on August 9, 2010 [34 favorites]
There's a whole class of interesting problems that have important real world applications for which no efficient algorithm is known. This would mean that no efficient algorithm exists. The most important consequence is that CS grad students can stop wasting time looking for efficient algorithms and get back to playing Starcraft.
posted by qxntpqbbbqxl at 12:39 AM on August 9, 2010 [34 favorites]
Outside of the intellectual interest, why?
There are many problems which are essentially equivalent to a kind of generic traveling salesman problem; you've got to schedule tasks or sequence actions to perform a goal. Algorithms that handle this kind of problem are used everywhere. There is another class of problems where relatively efficient solutions are known (sorting a list, for example) but it's been an open question whether these traveling salesman type problems can be handled with the same efficiency. If someone proves that P and NP are different classes, we don't have to try to invent algorithms for an NP situation to try to get P performance.
Hard to explain this in one comment. Sorry.
posted by twoleftfeet at 12:40 AM on August 9, 2010 [4 favorites]
There are many problems which are essentially equivalent to a kind of generic traveling salesman problem; you've got to schedule tasks or sequence actions to perform a goal. Algorithms that handle this kind of problem are used everywhere. There is another class of problems where relatively efficient solutions are known (sorting a list, for example) but it's been an open question whether these traveling salesman type problems can be handled with the same efficiency. If someone proves that P and NP are different classes, we don't have to try to invent algorithms for an NP situation to try to get P performance.
Hard to explain this in one comment. Sorry.
posted by twoleftfeet at 12:40 AM on August 9, 2010 [4 favorites]
The implications of this on applications such as cryptography, and on the general philosophical question of whether human creativity can be automated, would be profound.
I guess this means the Singularity is canceled.
posted by L.P. Hatecraft at 12:41 AM on August 9, 2010 [2 favorites]
I guess this means the Singularity is canceled.
posted by L.P. Hatecraft at 12:41 AM on August 9, 2010 [2 favorites]
OK, this is cool and all, but...
Not a big deal, really. In theory the halting problem is unsolvable. In reality, not only are no computers actually true Turing machines with an infinite amount of tape, but finding out if programs halt is -- except for the most pathological code -- completely tractable.
By the same token, NP-complete problems are in theory horrifying to attack. In reality, SAT and SMT solvers are making ridiculously quick work of large numbers of real world NP-complete problems.
There's a gap.
posted by effugas at 12:45 AM on August 9, 2010 [4 favorites]
Not a big deal, really. In theory the halting problem is unsolvable. In reality, not only are no computers actually true Turing machines with an infinite amount of tape, but finding out if programs halt is -- except for the most pathological code -- completely tractable.
By the same token, NP-complete problems are in theory horrifying to attack. In reality, SAT and SMT solvers are making ridiculously quick work of large numbers of real world NP-complete problems.
There's a gap.
posted by effugas at 12:45 AM on August 9, 2010 [4 favorites]
By the same token, NP-complete problems are in theory horrifying to attack.
They still are, no? At best, we can generate approximate answers in a realistic amount of human-time.
posted by Blazecock Pileon at 12:51 AM on August 9, 2010
They still are, no? At best, we can generate approximate answers in a realistic amount of human-time.
posted by Blazecock Pileon at 12:51 AM on August 9, 2010
Man, gotta say it's lucky the Futurama picked right for that one quick background gag with the folders labeled "P" and "NP".
posted by DoctorFedora at 1:00 AM on August 9, 2010
posted by DoctorFedora at 1:00 AM on August 9, 2010
MuffinMan wrote: I think you'll find the most important, unanswered, problem in the field of mathematics is how 10 people can put in $20 each towards a $200 restaurant bill and there always be $10 missing when the cash gets counted.
Ten mathematicians went out to dinner. At the end of the meal they each gave $20 to the waiter making a total of $200. The waiter was coming back with $50 change when he thought "Mathematicians are lousy tippers. I'll take my tip now, than you very much." The waiter kept $30 for himself and he gave each mathematician $2 each in change.
Q: Each mathematician paid $20 - $2 = $18 for a total of $180, plus the $30 that the waiter got which makes a total of $210. Where did the extra $10 come from?
A: The waiter added it to the bill for MuffinMan's table, which is why they were $10 short.
posted by Joe in Australia at 1:00 AM on August 9, 2010 [9 favorites]
Ten mathematicians went out to dinner. At the end of the meal they each gave $20 to the waiter making a total of $200. The waiter was coming back with $50 change when he thought "Mathematicians are lousy tippers. I'll take my tip now, than you very much." The waiter kept $30 for himself and he gave each mathematician $2 each in change.
Q: Each mathematician paid $20 - $2 = $18 for a total of $180, plus the $30 that the waiter got which makes a total of $210. Where did the extra $10 come from?
A: The waiter added it to the bill for MuffinMan's table, which is why they were $10 short.
posted by Joe in Australia at 1:00 AM on August 9, 2010 [9 favorites]
phrontist Outside of the intellectual interest, why? Cryptography?
It brings certainty to the state of things, and certainty is a very useful tool.
P=NP would be by far the preferable proof to have, of course. In terms of its practical consequences, P=NP would be the closest we could get to a proof of the existence of magic, or a God. If we had such a proof, that would mean that we could do, if not anything, a very great deal more than we currently can. It'd be a revolution in computation. It's not exactly the same as the Singularity, which is the point in time where a computer's general problem-solving ability, including the problem of how to improve its problem-solving ability, exceeds ours; after that we have no idea what would happen, and P=NP or P≠NP doesn't change that. The only influence it has is that if P=NP, we could produce better algorithms to advance computer problem-solving ability.
P≠NP is analogous to a philosophical/theological proof that magic doesn't work, or that there are no Gods at all, that there can't be any Gods, that it is therefore pointless to even consider the matter. As a mathematical proof, such assertions have a level of truth that greatly exceed mere human belief, memory, desire and experience. You can't decide to believe that 2+2=5. You can't have faith that it might, that even though there is no clear evidence for it, you can't believe and hope that under some circumstances maybe two and two might add up to five. Mathematically, it's disproved, and that's the end of the question.
If this proof is valid, it has enormous philosophical consequences. It would have few practical consequences, beyond freeing up a bit of time and money now wasted by people attempting to solve problems that would be known to be unsolvable, and of course dealing with the very real emotional consequences of this fact--relief and disappointment--would be among the practical consequences. It's a Very Big Question.
This is how Big a Question it is: if and when we ever established communication with another intelligent species, "Do you have a proof for P=NP?" should (and prior to this announcement, very likely would) be among the top five questions we would ask them, and expect them to ask us. "Can you disprove this proof we discovered for P≠NP?" is as important a question, if not as exciting.
posted by aeschenkarnos at 1:02 AM on August 9, 2010 [25 favorites]
It brings certainty to the state of things, and certainty is a very useful tool.
P=NP would be by far the preferable proof to have, of course. In terms of its practical consequences, P=NP would be the closest we could get to a proof of the existence of magic, or a God. If we had such a proof, that would mean that we could do, if not anything, a very great deal more than we currently can. It'd be a revolution in computation. It's not exactly the same as the Singularity, which is the point in time where a computer's general problem-solving ability, including the problem of how to improve its problem-solving ability, exceeds ours; after that we have no idea what would happen, and P=NP or P≠NP doesn't change that. The only influence it has is that if P=NP, we could produce better algorithms to advance computer problem-solving ability.
P≠NP is analogous to a philosophical/theological proof that magic doesn't work, or that there are no Gods at all, that there can't be any Gods, that it is therefore pointless to even consider the matter. As a mathematical proof, such assertions have a level of truth that greatly exceed mere human belief, memory, desire and experience. You can't decide to believe that 2+2=5. You can't have faith that it might, that even though there is no clear evidence for it, you can't believe and hope that under some circumstances maybe two and two might add up to five. Mathematically, it's disproved, and that's the end of the question.
If this proof is valid, it has enormous philosophical consequences. It would have few practical consequences, beyond freeing up a bit of time and money now wasted by people attempting to solve problems that would be known to be unsolvable, and of course dealing with the very real emotional consequences of this fact--relief and disappointment--would be among the practical consequences. It's a Very Big Question.
This is how Big a Question it is: if and when we ever established communication with another intelligent species, "Do you have a proof for P=NP?" should (and prior to this announcement, very likely would) be among the top five questions we would ask them, and expect them to ask us. "Can you disprove this proof we discovered for P≠NP?" is as important a question, if not as exciting.
posted by aeschenkarnos at 1:02 AM on August 9, 2010 [25 favorites]
Blazecock,
They're horrifying to get the absolute correct answer. It's however possible, even straightforward to get within engineering tolerances in realistic amounts of time. Not the sort of thing theory likes, but you know, the CPU you're running on was laid out by a solver.
The thing that's interesting is we're finding large amounts of problems that aren't actually fuzzy, are still being solvable using SAT/SMT solvers.
posted by effugas at 1:05 AM on August 9, 2010
They're horrifying to get the absolute correct answer. It's however possible, even straightforward to get within engineering tolerances in realistic amounts of time. Not the sort of thing theory likes, but you know, the CPU you're running on was laid out by a solver.
The thing that's interesting is we're finding large amounts of problems that aren't actually fuzzy, are still being solvable using SAT/SMT solvers.
posted by effugas at 1:05 AM on August 9, 2010
P≠NP is analogous to a philosophical/theological proof that magic doesn't work, or that there are no Gods at all, that there can't be any Gods, that it is therefore pointless to even consider the matter.
Oh come on. P=NP means there are no mathematical systems with asymmetric properties, i.e. if there's a fast way to verify correctness, there must be a fast way to calculate correctness.
That's _cool_ and _neat_ but don't break God into this. It's just a complexity relationship.
posted by effugas at 1:08 AM on August 9, 2010 [1 favorite]
Oh come on. P=NP means there are no mathematical systems with asymmetric properties, i.e. if there's a fast way to verify correctness, there must be a fast way to calculate correctness.
That's _cool_ and _neat_ but don't break God into this. It's just a complexity relationship.
posted by effugas at 1:08 AM on August 9, 2010 [1 favorite]
He's not saying that it has to do with God. He's saying that it is analogous to being able to prove/disprove it.
posted by Pope Guilty at 1:11 AM on August 9, 2010 [2 favorites]
posted by Pope Guilty at 1:11 AM on August 9, 2010 [2 favorites]
If Vinay Deolalikar is awarded the $1,000,000 Clay Millennium Prize for his proof of P≠NP, then I, Scott Aaronson, will personally supplement his prize by the amount of $200,000.
I'm not Scott Aaronson.
posted by metaplectic at 1:14 AM on August 9, 2010
I'm not Scott Aaronson.
posted by metaplectic at 1:14 AM on August 9, 2010
Not a big deal, really. In theory the halting problem is unsolvable. In reality, not only are no computers actually true Turing machines with an infinite amount of tape, but finding out if programs halt is -- except for the most pathological code -- completely tractable.
What? No way. Not even close. How many bytes are in a memory system? Unless you can completely a priori bound the data to some finite, small subset of state, there's no way this problem is tractable.
The halting problem grows at least exponentially with the number of state bits.
posted by spiderskull at 1:14 AM on August 9, 2010
What? No way. Not even close. How many bytes are in a memory system? Unless you can completely a priori bound the data to some finite, small subset of state, there's no way this problem is tractable.
The halting problem grows at least exponentially with the number of state bits.
posted by spiderskull at 1:14 AM on August 9, 2010
This is fascinating and completely over my head.
But the opening sentence just floors me with its combination of cosmic possibility and mundane detail.
I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts.
"I am pleased to announce a proof that God does not exist, which is attached in both Comic Sans and Tahoma."
posted by Cool Papa Bell at 1:17 AM on August 9, 2010 [30 favorites]
But the opening sentence just floors me with its combination of cosmic possibility and mundane detail.
I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts.
"I am pleased to announce a proof that God does not exist, which is attached in both Comic Sans and Tahoma."
posted by Cool Papa Bell at 1:17 AM on August 9, 2010 [30 favorites]
CPU you're running on was laid out by a solver
Actually, the CPU was very likely laid out by hand if it was from Intel (yes, really... all the transistors). AMD, on the other hand, uses synthesis tools. Even so, those solvers are heuristic (something like simulated annealing for place and route), which are just pragmatic approaches to getting something pretty close to optimal (but not provably so). Mind you, I am completely on your side in this debate -- I personally don't really care if something's an exact answer, as long as it's pretty damn good and meets the spec.
posted by spiderskull at 1:17 AM on August 9, 2010
Actually, the CPU was very likely laid out by hand if it was from Intel (yes, really... all the transistors). AMD, on the other hand, uses synthesis tools. Even so, those solvers are heuristic (something like simulated annealing for place and route), which are just pragmatic approaches to getting something pretty close to optimal (but not provably so). Mind you, I am completely on your side in this debate -- I personally don't really care if something's an exact answer, as long as it's pretty damn good and meets the spec.
posted by spiderskull at 1:17 AM on August 9, 2010
I think you'll find the most important, unanswered, problem in the field of mathematics is how 10 people can put in $20 each towards a $200 restaurant bill and there always be $10 missing when the cash gets counted.
With all due deference to the Australian Joe's hypothesis, I submit that a simpler solution would be to blame the missing dinero on the nerdy white guy.
posted by The Potate at 1:18 AM on August 9, 2010
With all due deference to the Australian Joe's hypothesis, I submit that a simpler solution would be to blame the missing dinero on the nerdy white guy.
posted by The Potate at 1:18 AM on August 9, 2010
What? No way. Not even close. How many bytes are in a memory system? Unless you can completely a priori bound the data to some finite, small subset of state, there's no way this problem is tractable.
The halting problem grows at least exponentially with the number of state bits.
No, no it doesn't.
The money quote:
“It’s being used, for example,” Cook says, “to automatically prove that Windows device-driver dispatch routines will always eventually stop trying to handle an event such as a mouse-click or an attempt to save a file.”More important is SAGE. SAGE is a fuzzer -- a mechanism for generating randomized inputs that stress programs into crashing. Only, it turns out that if instead of being random, you actually intelligently guide the generation of malicious files, you get far higher hit rates.
SAGE works by tracking the flow of execution through a program, with all the various bitwise transforms in memory. When a potentially interesting section is found -- say, a potential crash if somehow n=87113, the Z3 Solver will be used to find a file that, if inserted at the top of the program, will filter into n=87113 twenty functions in.
About a third of the Windows 7 bugs were found this way.
I promise you, at the limit this problem is in fact NP-complete. I also tell you, real world systems are not in fact operating at the theoretical limits.
posted by effugas at 1:25 AM on August 9, 2010 [2 favorites]
As twoleftfeet explained, the "traveling salesman problem" has many practical applications. Digital radio communication receivers rely heavily on these concepts.
Unfortunately, I don't think this will help in any way with HP's recent traveling salesman problem.
posted by three blind mice at 1:25 AM on August 9, 2010 [3 favorites]
Unfortunately, I don't think this will help in any way with HP's recent traveling salesman problem.
posted by three blind mice at 1:25 AM on August 9, 2010 [3 favorites]
Outside of the intellectual interest, why? Cryptography?
It's not really important in a real world sense if it's proven true. Everyone has been assuming it's been true for a long time. But it's possible that whatever method was used to do the proof, that method might yeild some interesting new insights.
On the other had, if the opposite were proven true, that P = NP, then that could have some effect, but probably not much of an effect if there was a 'high exponent' (i.e. an algorithm with an O(n9) isn't practical even though it's in P)
P≠NP is analogous to a philosophical/theological proof that magic doesn't work, or that there are no Gods at all, that there can't be any Gods, that it is therefore pointless to even consider the matter.
Again, this is totally absurd and bordering on jibberish.
---
posted by delmoi at 1:27 AM on August 9, 2010 [8 favorites]
It's not really important in a real world sense if it's proven true. Everyone has been assuming it's been true for a long time. But it's possible that whatever method was used to do the proof, that method might yeild some interesting new insights.
On the other had, if the opposite were proven true, that P = NP, then that could have some effect, but probably not much of an effect if there was a 'high exponent' (i.e. an algorithm with an O(n9) isn't practical even though it's in P)
In terms of its practical consequences, P=NP would be the closest we could get to a proof of the existence of magic, or a God.That, is a completly ridiculous. The P=NP question seems to attract as much crazy nonsense in people who know something about computers as "Mysterious Quantum" stuff attracts in lots of people. Ugh.
If we had such a proof, that would mean that we could do, if not anything, a very great deal more than we currently can.Again, it depends on the exponent. Just because something is in P doesn't make it solvable. There was a proof a copule years ago showing you could factor large polynomials in P time, but the exponent was so high it wasn't actually practical. (Which is why P = NP actually has no baring on public key cryptography, btw)
Again, this is totally absurd and bordering on jibberish.
---
If Vinay Deolalikar is awarded the $1,000,000 Clay Millennium Prize for his proof of P≠NP, then I, Scott Aaronson, will personally supplement his prize by the amount of $200,000.Interesting. Scott Aaronson certainly seems to know a lot about these things. If he doubts the proof, that's good reason to doubt it. The thing is, people claim to have proofs one way or the other (i.e. P != NP or P = NP) all the time. A new claim of proof isn't news. It would be news if it was peer reviewed, which this seemed to have been. And it sounds like it doesn't strike Aaronson as being crackpot central. So it will be interesting to see. It could take years to verify the proof if it's real. Should take less time to disprove it. (ironically)
posted by delmoi at 1:27 AM on August 9, 2010 [8 favorites]
effugas -- my mistake, I was thinking of formal verification of processors.
posted by spiderskull at 1:28 AM on August 9, 2010
posted by spiderskull at 1:28 AM on August 9, 2010
Cool Papa Bell, I think you'll find that most proofs that God exists are in Comic Sans.
posted by cthuljew at 1:29 AM on August 9, 2010 [10 favorites]
posted by cthuljew at 1:29 AM on August 9, 2010 [10 favorites]
If he doubts the proof, that's good reason to doubt it.
He seems to be doubting it just on general principle though. From the Scott Aaronson link:
Is the proof right or isn’t it? C’mon, it’s been like three hours since you first saw it—what’s taking you so long?” Well, somehow, I haven’t yet found the opportunity to study this 103-page manuscript in detail. Furthermore, I don’t plan to interrupt my vacation time in Israel and Greece to do so, unless experts who have studied the paper in detail start telling me that I should.
posted by juv3nal at 1:32 AM on August 9, 2010
He seems to be doubting it just on general principle though. From the Scott Aaronson link:
Is the proof right or isn’t it? C’mon, it’s been like three hours since you first saw it—what’s taking you so long?” Well, somehow, I haven’t yet found the opportunity to study this 103-page manuscript in detail. Furthermore, I don’t plan to interrupt my vacation time in Israel and Greece to do so, unless experts who have studied the paper in detail start telling me that I should.
posted by juv3nal at 1:32 AM on August 9, 2010
What? No way. Not even close. How many bytes are in a memory system? Unless you can completely a priori bound the data to some finite, small subset of state, there's no way this problem is tractable.The thing to understand is that when it comes to the Halting problem, there's no difference between what a computer is "capable" of doing or what a person is "capable" of. It's all just math. So if you look at a program like this:
The halting problem grows at least exponentially with the number of state bits.
while(int i <>
Will it halt? Obviously not. A ton of software isn't much more complicated then that. Especially something like driver software, where you don't want to have any NP algorithms that could potentially never halt.
Remember, the Halting problem is a Turing acceptable function. You can return true (will halt) if you simulate a program and it stops. You can return false if you simulate a program and it ever duplicates it's state (that means it's in a loop). You can simplify the program by not calculating anything that's going to be used in it's halting criteria, etc.
Anyway, the halting problem is different then solving SAT (which is one of the canonical NP problems). SAT solvers try to simplify Boolean expressions to make it easier to figure out if they have a solution, without going through all the possible bits.posted by delmoi at 1:35 AM on August 9, 2010
Er, crap.
The code should have been
posted by delmoi at 1:37 AM on August 9, 2010
The code should have been
while(int i = 0 < 10){i = (i+1) % 9;}posted by delmoi at 1:37 AM on August 9, 2010
Actually, P=NP is less cool than NP->P -- give me a way to solve any NP complete problem in reasonable constant polynomial time, and yes, you'll totally have my attention.
posted by effugas at 1:40 AM on August 9, 2010
posted by effugas at 1:40 AM on August 9, 2010
For anyone who is curious, the answer to Q: Each mathematician paid $20 - $2 = $18 for a total of $180, plus the $30 that the waiter got which makes a total of $210. Where did the extra $10 come from? is that you actually don't add the extra 30 back in at the end. It's included in the 20-2 in the beginning of the problem.
Assuming 10 guests, who each paid 20 dollars, you get a total of 200. The waiter is originally going to return 50 dollars, so the original bill is 150.
If the waiter only returns 2 to each guest, then each guest is contributing 18. If the waiter was honest and had returned the entire amount of the change, each guest would be contributing 15.
18-15 = 3. 180-150 = 30.
posted by FritoKAL at 1:41 AM on August 9, 2010
Assuming 10 guests, who each paid 20 dollars, you get a total of 200. The waiter is originally going to return 50 dollars, so the original bill is 150.
If the waiter only returns 2 to each guest, then each guest is contributing 18. If the waiter was honest and had returned the entire amount of the change, each guest would be contributing 15.
18-15 = 3. 180-150 = 30.
posted by FritoKAL at 1:41 AM on August 9, 2010
If he doubts the proof, that's good reason to doubt it.
He hasn't read it.
posted by Blazecock Pileon at 1:42 AM on August 9, 2010 [2 favorites]
He hasn't read it.
posted by Blazecock Pileon at 1:42 AM on August 9, 2010 [2 favorites]
I remember one NP problem had something to do with producing two matching strings from two sets of substrings. For instance, using set1 = ("ab", "abb", ba") and set2 = ("bab", "abb", "aba") determine whether you can make a pair of identical strings built out of those substrings. Can anyone remind me what this problem is called?
posted by Joe in Australia at 1:42 AM on August 9, 2010
posted by Joe in Australia at 1:42 AM on August 9, 2010
It's however possible, even straightforward to get within engineering tolerances in realistic amounts of time.
What those tolerances are might depend pretty heavily on what's being engineered. As far as protein folding goes, it still seems to be fairly computationally intractable, to get a reasonably definitive answer for any given input, not even taking into account chaperones and other cofactors.
posted by Blazecock Pileon at 1:48 AM on August 9, 2010
What those tolerances are might depend pretty heavily on what's being engineered. As far as protein folding goes, it still seems to be fairly computationally intractable, to get a reasonably definitive answer for any given input, not even taking into account chaperones and other cofactors.
posted by Blazecock Pileon at 1:48 AM on August 9, 2010
What those tolerances are might depend pretty heavily on what's being engineered. As far as protein folding goes, it still seems to be fairly computationally intractable, to get a reasonably definitive answer for any given input, not even taking into account chaperones and other cofactors.
Protein folding is straight up fascinating precisely because it's literally (in the actual, real meaning of the word literally) a distributed computation problem. I think it will eventually fall, though, just because it's a domain in which if the system is too fragile, it collapses.
That, and human pattern matching seems to be helping too much.
posted by effugas at 1:53 AM on August 9, 2010
Protein folding is straight up fascinating precisely because it's literally (in the actual, real meaning of the word literally) a distributed computation problem. I think it will eventually fall, though, just because it's a domain in which if the system is too fragile, it collapses.
That, and human pattern matching seems to be helping too much.
posted by effugas at 1:53 AM on August 9, 2010
That seems old fashioned, BP. I think proteins are old enough to be out on their own.
posted by Pope Guilty at 1:53 AM on August 9, 2010 [3 favorites]
posted by Pope Guilty at 1:53 AM on August 9, 2010 [3 favorites]
delmoi That, is a completly ridiculous. The P=NP question seems to attract as much crazy nonsense in people who know something about computers as "Mysterious Quantum" stuff attracts in lots of people. Ugh.
"If P=NP is proved [...] mathematics would be transformed, because computers could find a formal proof of any theorem which has a proof of reasonable length. This is because formal proofs (say in Zermelo–Fraenkel set theory) are easily recognized by efficient algorithms, and hence bounded proof existence is in NP. Although the formal proofs may not be intelligible to humans, the problem of finding intelligible proofs would be reduced to that of finding a good recognition algorithm for formal proofs. Similar remarks apply to the fundamental problems of artificial intelligence: planning, natural language understanding, vision, and even creative endeavors such as composing music and writing novels. In each case, success would depend on finding good algorithms for recognizing good results, and this fundamental problem itself would be aided by the SAT solver by allowing easy testing of recognition theories." -- Stephen Cook, 2003.
I think you're mistaking the idea of considering things to be really important, for believing in crazy nonsense about them. I'm just making an analogy there. I suspect that what bothers you is the mere mention of the concept of consideration of the existence of God; personally I don't believe in any gods either, but I can see that a formal proof or disproof would be of immense importance to believers. But perhaps (non-)existence of God(s) is too important though, as you say.
posted by aeschenkarnos at 2:47 AM on August 9, 2010 [1 favorite]
"If P=NP is proved [...] mathematics would be transformed, because computers could find a formal proof of any theorem which has a proof of reasonable length. This is because formal proofs (say in Zermelo–Fraenkel set theory) are easily recognized by efficient algorithms, and hence bounded proof existence is in NP. Although the formal proofs may not be intelligible to humans, the problem of finding intelligible proofs would be reduced to that of finding a good recognition algorithm for formal proofs. Similar remarks apply to the fundamental problems of artificial intelligence: planning, natural language understanding, vision, and even creative endeavors such as composing music and writing novels. In each case, success would depend on finding good algorithms for recognizing good results, and this fundamental problem itself would be aided by the SAT solver by allowing easy testing of recognition theories." -- Stephen Cook, 2003.
I think you're mistaking the idea of considering things to be really important, for believing in crazy nonsense about them. I'm just making an analogy there. I suspect that what bothers you is the mere mention of the concept of consideration of the existence of God; personally I don't believe in any gods either, but I can see that a formal proof or disproof would be of immense importance to believers. But perhaps (non-)existence of God(s) is too important though, as you say.
posted by aeschenkarnos at 2:47 AM on August 9, 2010 [1 favorite]
I remember one NP problem had something to do with producing two matching strings from two sets of substrings. For instance, using set1 = ("ab", "abb", ba") and set2 = ("bab", "abb", "aba") determine whether you can make a pair of identical strings built out of those substrings. Can anyone remind me what this problem is called?
This is the Post Correspondence Problem.
posted by pennybacker at 2:56 AM on August 9, 2010 [3 favorites]
This is the Post Correspondence Problem.
posted by pennybacker at 2:56 AM on August 9, 2010 [3 favorites]
Ah, thanks. And following those links took me to this contest, which looks a lot of fun.
posted by Joe in Australia at 3:18 AM on August 9, 2010
posted by Joe in Australia at 3:18 AM on August 9, 2010
aeschenkarnos,
P=NP is a factual bit, not an empirical process with useful time constraints. For example, we got that great "Primes Is In P" paper a while ago, but nobody uses the technique because Miller-Rabin is much, much faster. So the statement:
"computers could find a formal proof of any theorem which has a proof of reasonable length."
...this statement is false. P=NP could be completely proved true, and still not have anything of operational use.
posted by effugas at 3:18 AM on August 9, 2010 [2 favorites]
P=NP is a factual bit, not an empirical process with useful time constraints. For example, we got that great "Primes Is In P" paper a while ago, but nobody uses the technique because Miller-Rabin is much, much faster. So the statement:
"computers could find a formal proof of any theorem which has a proof of reasonable length."
...this statement is false. P=NP could be completely proved true, and still not have anything of operational use.
posted by effugas at 3:18 AM on August 9, 2010 [2 favorites]
aeschenkarnos: You're missing the fact that just because a problem is in P time doesn't mean that it's actually doable in real, practical time, because it all depends on the exponent.
Also, as to whether or not a P time SAT solver could prove every mathematical theory: I'm a little skeptical. Isn't "This program will halt" a mathematical statement? Solving NP Problems doesn't answer the halting problem.
posted by delmoi at 3:20 AM on August 9, 2010 [1 favorite]
Also, as to whether or not a P time SAT solver could prove every mathematical theory: I'm a little skeptical. Isn't "This program will halt" a mathematical statement? Solving NP Problems doesn't answer the halting problem.
posted by delmoi at 3:20 AM on August 9, 2010 [1 favorite]
P=NP is a factual bit, not an empirical process with useful time constraints. For example, we got that great "Primes Is In P" paper a while ago, but nobody uses the technique because Miller-Rabin is much, much faster. So the statement:
I was going to mention that, but according to Wikipedia:
posted by delmoi at 3:23 AM on August 9, 2010 [1 favorite]
I was going to mention that, but according to Wikipedia:
It is suspected to be outside of all three of the complexity classes P, NP-complete, and co-NP-complete. If it could be proved that it is in either NP-Complete or co-NP-Complete, that would imply NP = co-NP. That would be a very surprising result, and therefore integer factorization is widely suspected to be outside both of those classes. Many people have tried to find classical polynomial-time algorithms for it and failed, and therefore it is widely suspected to be outside P.(Which, if true, would mean that even if P = NP, it still wouldn't help with factoring large prime numbers)
posted by delmoi at 3:23 AM on August 9, 2010 [1 favorite]
delmoi: I thought the Halting Problem was in NP, but I may be wrong there.
And you're right, just because a problem is in P doesn't mean you can solve it in a reasonable amount of time because it might still be incredibly complicated and require a lot of inputs to do anything useful with, but if it's in NP it's going to get intractable almost immediately as you scale up the inputs, so P's still very preferable.
posted by mathw at 3:32 AM on August 9, 2010
And you're right, just because a problem is in P doesn't mean you can solve it in a reasonable amount of time because it might still be incredibly complicated and require a lot of inputs to do anything useful with, but if it's in NP it's going to get intractable almost immediately as you scale up the inputs, so P's still very preferable.
posted by mathw at 3:32 AM on August 9, 2010
"P" is clearly not equal to "NP".
"NP" has an "N" in it, whereas "P" is just plain "P".
(Prize money please.)
posted by run"monty at 3:37 AM on August 9, 2010 [12 favorites]
"NP" has an "N" in it, whereas "P" is just plain "P".
(Prize money please.)
posted by run"monty at 3:37 AM on August 9, 2010 [12 favorites]
delmoi: I thought the Halting Problem was in NP, but I may be wrong there.
Well, you are definitely wrong. Way off. All NP problems are solvable on a regular computer given enough (but a finite amount of) time.
P and !P deal with how much time it takes to solve a problem. P problems are ones that can be solved with a time of O(np). Exponential problems are ones that can be solved in time O(kn). In other words, P time problems are ones that take n to the p steps to solve for a given input size n and a p that is specific to the problem.
Exponential problems take k to then n steps, where n is the number of elements in the problem. (plus some other terms that aren't important).
So we know NP problems can be solved on a regular computer in exponential time. The question is whether or not they can be solved in polynomial time.
NP stands for "non-deterministic polynomial time". It means a problem that can be solved on a non-deterministic Turing machine in polynomial time. The question is whether or not it can be solved on a deterministic (or ordinary) Turing machine in polynomial time.
It has nothing to do with the halting problem. N machines can't solve the halting problem any better then regular machines.
posted by delmoi at 3:55 AM on August 9, 2010 [3 favorites]
Well, you are definitely wrong. Way off. All NP problems are solvable on a regular computer given enough (but a finite amount of) time.
P and !P deal with how much time it takes to solve a problem. P problems are ones that can be solved with a time of O(np). Exponential problems are ones that can be solved in time O(kn). In other words, P time problems are ones that take n to the p steps to solve for a given input size n and a p that is specific to the problem.
Exponential problems take k to then n steps, where n is the number of elements in the problem. (plus some other terms that aren't important).
So we know NP problems can be solved on a regular computer in exponential time. The question is whether or not they can be solved in polynomial time.
NP stands for "non-deterministic polynomial time". It means a problem that can be solved on a non-deterministic Turing machine in polynomial time. The question is whether or not it can be solved on a deterministic (or ordinary) Turing machine in polynomial time.
It has nothing to do with the halting problem. N machines can't solve the halting problem any better then regular machines.
posted by delmoi at 3:55 AM on August 9, 2010 [3 favorites]
Intellectual interest is not only real importance, it is one of the few REAL importances.
posted by DU at 4:16 AM on August 9, 2010 [5 favorites]
posted by DU at 4:16 AM on August 9, 2010 [5 favorites]
I think you'll find the most important, unanswered, problem in the field of mathematics is how 10 people can put in $20 each towards a $200 restaurant bill and there always be $10 missing when the cash gets counted.
That's not a math problem. You can trust numbers. People? Not so much.
posted by billyfleetwood at 4:18 AM on August 9, 2010
That's not a math problem. You can trust numbers. People? Not so much.
posted by billyfleetwood at 4:18 AM on August 9, 2010
delmoi: I thought the Halting Problem was in NP, but I may be wrong there.
Well, you are definitely wrong. Way off.
No, you (delmoi) are wrong: Mathw isn't even wrong. P and NP are complexity classes. The Halting Problem is not a complexity problem. Putting it into P or NP is almost as ridiculous as putting jam into them.
posted by DU at 4:24 AM on August 9, 2010
Well, you are definitely wrong. Way off.
No, you (delmoi) are wrong: Mathw isn't even wrong. P and NP are complexity classes. The Halting Problem is not a complexity problem. Putting it into P or NP is almost as ridiculous as putting jam into them.
posted by DU at 4:24 AM on August 9, 2010
Here is an entertaining list of previous attempts. Best of luck to Dr Deolalikar, however.
(via)
posted by iati at 4:24 AM on August 9, 2010 [1 favorite]
(via)
posted by iati at 4:24 AM on August 9, 2010 [1 favorite]
Come on, we figured out whether or not P = NP in grade school, didn't we?
(P = NP) iff (N = 1 or P = 0)
posted by kmz at 4:31 AM on August 9, 2010 [6 favorites]
(P = NP) iff (N = 1 or P = 0)
posted by kmz at 4:31 AM on August 9, 2010 [6 favorites]
P=NP would be by far the preferable proof to have.
Not if you want to live in a universe that makes sense.
posted by Obscure Reference at 4:36 AM on August 9, 2010 [4 favorites]
Not if you want to live in a universe that makes sense.
posted by Obscure Reference at 4:36 AM on August 9, 2010 [4 favorites]
I think you'll find the most important, unanswered, problem in the field of mathematics is how 10 people can put in $20 each towards a $200 restaurant bill and there always be $10 missing when the cash gets counted.
This is one of the important questions in the burgeoning field of bistromathics, along with why no one ever turns up at the time they say they will, and why the number of people booked will bear no relation to the number who turn up.
posted by Electric Dragon at 4:49 AM on August 9, 2010 [4 favorites]
This is one of the important questions in the burgeoning field of bistromathics, along with why no one ever turns up at the time they say they will, and why the number of people booked will bear no relation to the number who turn up.
posted by Electric Dragon at 4:49 AM on August 9, 2010 [4 favorites]
IIRC, in one of the Laundry books (by MeFi's own cstross), solving P=NP is one of the things that potentially opens a gateway to the Dark Dimensions and lets nameless horrors into our world, so anyone who does either gets absorbed into the secret mystical intelligence agencies, or... gets disappeared. I hope that this fellow spends his million pretty quickly.
posted by Halloween Jack at 5:11 AM on August 9, 2010 [1 favorite]
posted by Halloween Jack at 5:11 AM on August 9, 2010 [1 favorite]
"I am pleased to announce a proof that God does not exist, which is attached in both Comic Sans and Tahoma."
Of course, the Tahoma is actually redundant.
posted by UbuRoivas at 5:11 AM on August 9, 2010
Of course, the Tahoma is actually redundant.
posted by UbuRoivas at 5:11 AM on August 9, 2010
If he collects the $1,000,000, he can pay the restaurant bill by himself. So he'll have solved two important, unanswered problems.
posted by Joe Beese at 5:27 AM on August 9, 2010 [4 favorites]
posted by Joe Beese at 5:27 AM on August 9, 2010 [4 favorites]
I think you'll find that most proofs that God exists are in Comic Sans.
I think you'll find that comic Sans proves that God doesn't exist.
posted by dirtdirt at 5:30 AM on August 9, 2010 [6 favorites]
I think you'll find that comic Sans proves that God doesn't exist.
posted by dirtdirt at 5:30 AM on August 9, 2010 [6 favorites]
The existence of mosquitoes already does that, which makes Comic Sans even more useless.
posted by UbuRoivas at 5:41 AM on August 9, 2010
posted by UbuRoivas at 5:41 AM on August 9, 2010
Oh man, I so want to understand even just the basics of this, but I'm completely failing. The words are in English, but when you put them in THAT order...
Anybody got an explanation that's not just for laymen, but for really, really stupid laymen?
posted by grapefruitmoon at 5:43 AM on August 9, 2010
Anybody got an explanation that's not just for laymen, but for really, really stupid laymen?
posted by grapefruitmoon at 5:43 AM on August 9, 2010
I think you'll find that comic Sans proves that God doesn't exist.
I think it proves the Devil uses PowerPoint.
posted by Blazecock Pileon at 5:43 AM on August 9, 2010
I think it proves the Devil uses PowerPoint.
posted by Blazecock Pileon at 5:43 AM on August 9, 2010
This is one of the best MeFi discussions I've read in a long time. It seriously revives my faith in the site.
posted by nasreddin at 5:51 AM on August 9, 2010
posted by nasreddin at 5:51 AM on August 9, 2010
Also, as to whether or not a P time SAT solver could prove every mathematical theory: I'm a little skeptical. Isn't "This program will halt" a mathematical statement? Solving NP Problems doesn't answer the halting problem.
It would not be able to prove every mathematical theory, but it could be used to efficiently check whether a proof up to length k for a theorem exists: You can already efficiently check whether a proof is valid, what P time SAT would give you is a faster way to find a proof of length k if it exists, starting from a set of axioms, without having to try each possible proof. You could then ask: Is there a proof of less than 1000 pages for this theorem? Less than 10000? Obviously, in general, you could not determine that the theorem is false - there might be one just one page longer - and the proofs would not look nice at all. But in the unlikely event that you have proven P=NP, hopefully with a small exponent, it would not be stupid to implement your algorithm and let it try to find proofs of reasonable length for the other Millenium problems. Could get you another million dollars...
(Which, if true, would mean that even if P = NP, it still wouldn't help with factoring large prime numbers)
No, it means that factoring large integers which are the product of two large primes is assumed not to be one of the hard NP problems. It would be possible to find a factoring algorithm in P without P=NP. But if P=NP, then factoring is in P. Sloppy formulation, check this for formal details.
posted by ltl at 6:01 AM on August 9, 2010 [1 favorite]
It would not be able to prove every mathematical theory, but it could be used to efficiently check whether a proof up to length k for a theorem exists: You can already efficiently check whether a proof is valid, what P time SAT would give you is a faster way to find a proof of length k if it exists, starting from a set of axioms, without having to try each possible proof. You could then ask: Is there a proof of less than 1000 pages for this theorem? Less than 10000? Obviously, in general, you could not determine that the theorem is false - there might be one just one page longer - and the proofs would not look nice at all. But in the unlikely event that you have proven P=NP, hopefully with a small exponent, it would not be stupid to implement your algorithm and let it try to find proofs of reasonable length for the other Millenium problems. Could get you another million dollars...
(Which, if true, would mean that even if P = NP, it still wouldn't help with factoring large prime numbers)
No, it means that factoring large integers which are the product of two large primes is assumed not to be one of the hard NP problems. It would be possible to find a factoring algorithm in P without P=NP. But if P=NP, then factoring is in P. Sloppy formulation, check this for formal details.
posted by ltl at 6:01 AM on August 9, 2010 [1 favorite]
Well, if P≠NP, there's hope that NP=PSPACE, which would be far cooler than P=NP.
posted by erdferkel at 6:02 AM on August 9, 2010
posted by erdferkel at 6:02 AM on August 9, 2010
Someone correct me if I'm wrong, but this is my understanding of NP-completeness using the example of the Travelling Salesman problem:
A salesman is in a country where there is, say, 100 cities he wants to visit. He wants to visit each of those cities in the shortest amount of time possible. He knows how far away any given city is from any other given city, and is trying to work out the best route.
There are many different approaches to solving that problem (i.e., algorithms), but in order to get the best possible answer, because it's an NP-complete problem, we need to calculate and compare every possible combination of routes. Brute force the answer, essentially. We can find relatively efficient routes by other means, but we can't know for sure that we have the absolute best route possible without brute force verification.
So if P != NP, this holds true. But if P = NP, there exists an algorithm to solve this (and any other NP-complete) problem, even if we don't know it yet.
Yes?
posted by chmmr at 6:04 AM on August 9, 2010 [1 favorite]
A salesman is in a country where there is, say, 100 cities he wants to visit. He wants to visit each of those cities in the shortest amount of time possible. He knows how far away any given city is from any other given city, and is trying to work out the best route.
There are many different approaches to solving that problem (i.e., algorithms), but in order to get the best possible answer, because it's an NP-complete problem, we need to calculate and compare every possible combination of routes. Brute force the answer, essentially. We can find relatively efficient routes by other means, but we can't know for sure that we have the absolute best route possible without brute force verification.
So if P != NP, this holds true. But if P = NP, there exists an algorithm to solve this (and any other NP-complete) problem, even if we don't know it yet.
Yes?
posted by chmmr at 6:04 AM on August 9, 2010 [1 favorite]
Here's a comment I made at MetaChat that tries to explain what all this is about for people that don't know what it's all about.
posted by Wolfdog at 6:22 AM on August 9, 2010 [15 favorites]
posted by Wolfdog at 6:22 AM on August 9, 2010 [15 favorites]
Great comment Wolfdog, thanks!
posted by grapefruitmoon at 6:24 AM on August 9, 2010
posted by grapefruitmoon at 6:24 AM on August 9, 2010
Anybody got an explanation that's not just for laymen, but for really, really stupid laymen?
Some kinds of problems are quick to solve using computers.
Others are difficult or time-consuming to solve using computers. At the level of "If you harnessed all the matter and energy in the observable universe and used them to compute the answer to this problem, it would still take billions or trillions of years."
If P=NP, then at least some of those difficult/time-consuming problems turn out to have relatively quick and easy solutions that we just don't know yet. But relatively quick could still mean that you have to harness the matter and energy of a few solar systems and it still takes thousands of years. If P!=NP, then those quick and easy solutions have been shown to be nonexistent.
posted by ROU_Xenophobe at 6:33 AM on August 9, 2010
Some kinds of problems are quick to solve using computers.
Others are difficult or time-consuming to solve using computers. At the level of "If you harnessed all the matter and energy in the observable universe and used them to compute the answer to this problem, it would still take billions or trillions of years."
If P=NP, then at least some of those difficult/time-consuming problems turn out to have relatively quick and easy solutions that we just don't know yet. But relatively quick could still mean that you have to harness the matter and energy of a few solar systems and it still takes thousands of years. If P!=NP, then those quick and easy solutions have been shown to be nonexistent.
posted by ROU_Xenophobe at 6:33 AM on August 9, 2010
Anybody got an explanation that's not just for laymen, but for really, really stupid laymen?
This is what I understand of it, as a layman, at least in terms of the consequences of it:
Imagine that you have a list of all mathematical problems.
Let's try dividing these into groups, based on various criteria.
The first criteria is: Given an answer to a given problem, can the solution be verified 'quickly'*. The set of all problems for which this is true is called 'NP'.
The second criteria is: Is it possible to FIND a solution to a given problem 'quickly'. The set of all problems for which this is true is called 'P'.
It was proven a long time ago that if a problem is in P, it is also in NP -- that is -- if it's possible to solve it quickly, it's possible to verify a solution quickly (this is pretty much common sense).
The open question was if something was in NP, was it also in P. That is -- if it's possible to verify a solution to a problem quickly, is it also possible to solve it quickly. If true, this would mean that P = NP. The two sets would be identical.
One practical effect of P = NP would mean that public-key encryption would be on shaky footing because it depends on the fact that factoring large numbers into primes is in NP, but not P. If P = NP, then a polynomial time solution to cracking any encryption must exist.
Proving P != NP is an important proof, but it's what everyone expected to be true anyway, so it doesn't radically change our understanding of the universe or anything like that.
*'quickly' in this case means in 'Polynomial time'. This can actually end up being a very, very, long time for some problems.
posted by empath at 6:37 AM on August 9, 2010 [1 favorite]
This is what I understand of it, as a layman, at least in terms of the consequences of it:
Imagine that you have a list of all mathematical problems.
Let's try dividing these into groups, based on various criteria.
The first criteria is: Given an answer to a given problem, can the solution be verified 'quickly'*. The set of all problems for which this is true is called 'NP'.
The second criteria is: Is it possible to FIND a solution to a given problem 'quickly'. The set of all problems for which this is true is called 'P'.
It was proven a long time ago that if a problem is in P, it is also in NP -- that is -- if it's possible to solve it quickly, it's possible to verify a solution quickly (this is pretty much common sense).
The open question was if something was in NP, was it also in P. That is -- if it's possible to verify a solution to a problem quickly, is it also possible to solve it quickly. If true, this would mean that P = NP. The two sets would be identical.
One practical effect of P = NP would mean that public-key encryption would be on shaky footing because it depends on the fact that factoring large numbers into primes is in NP, but not P. If P = NP, then a polynomial time solution to cracking any encryption must exist.
Proving P != NP is an important proof, but it's what everyone expected to be true anyway, so it doesn't radically change our understanding of the universe or anything like that.
*'quickly' in this case means in 'Polynomial time'. This can actually end up being a very, very, long time for some problems.
posted by empath at 6:37 AM on August 9, 2010 [1 favorite]
cthuljew: "I think you'll find that most proofs that God exists are in Comic Sans."
These five weren't even typed, as I recall.
posted by l33tpolicywonk at 6:38 AM on August 9, 2010
These five weren't even typed, as I recall.
posted by l33tpolicywonk at 6:38 AM on August 9, 2010
No, you (delmoi) are wrong: Mathw isn't even wrong. P and NP are complexity classes. The Halting Problem is not a complexity problem. Putting it into P or NP is almost as ridiculous as putting jam into them.
The halting problem for Turing machines (or any other equivalently powerful device) is definitely a complexity problem - it's complete for the class RE. The complexity zoo seems to be down right now, but wikipedia might convince you.
In fact, every decision problem can be seen as a complexity problem, although complexity theorists mostly prefer the classes far below RE to RE and the ones above it.
posted by erdferkel at 6:56 AM on August 9, 2010 [3 favorites]
The halting problem for Turing machines (or any other equivalently powerful device) is definitely a complexity problem - it's complete for the class RE. The complexity zoo seems to be down right now, but wikipedia might convince you.
In fact, every decision problem can be seen as a complexity problem, although complexity theorists mostly prefer the classes far below RE to RE and the ones above it.
posted by erdferkel at 6:56 AM on August 9, 2010 [3 favorites]
So, I guess we're not going back to the warm regard and comfort of a god who really cares.
posted by adipocere at 7:11 AM on August 9, 2010 [1 favorite]
posted by adipocere at 7:11 AM on August 9, 2010 [1 favorite]
If he doubts the proof, that's good reason to doubt it.Scott Aaronson has not read all the details, being on vacation and all. But he is willing to pay $200,000 in case the proof does in fact work. And he knows what he's talking about (e.g., he is the zoo keeper of the complexity zoo). There are a lot of papers out there claiming to have solved P=NP or P!=NP. Most of them are so crappy they are not even wrong. This instance seems to be a much more serious effort. But a lot is known about which proof techniques can not work for this question and if Scott's gut is not convinced after skimming the proof outline, I would go with that until there is some serious peer review. Which should probably not take years, as this proof is not even near Fermat's Last Theorem proof complexity.
He hasn't read it.
posted by ltl at 7:17 AM on August 9, 2010
I just read it and there's an error in his reasoning; he got a sign around the wrong way on page 56. Oh well, maybe next time.
posted by Joe Chip at 7:25 AM on August 9, 2010 [1 favorite]
posted by Joe Chip at 7:25 AM on August 9, 2010 [1 favorite]
Some kinds of problems are quick to solve using computers.
Others are difficult or time-consuming to solve using computers. At the level of "If you harnessed all the matter and energy in the observable universe and used them to compute the answer to this problem, it would still take billions or trillions of years."
If P=NP, then at least some of those difficult/time-consuming problems turn out to have relatively quick and easy solutions that we just don't know yet.
The problem with that explanation is that the concept of P and NP do NOT map to being "easy" or "hard". Lots of problems in P are too hard actually do, for example, while lots of problems in NP have useful heuristics that let you do them quickly (but not necessarily perfectly)
Really, in order to understand it, you have to understand the concept of a Turing machine, and what it would mean for a TM to be in multiple states at once. If you get that, then it's actually pretty simple to explain. But getting to that point takes a while.
Without that, it's kind of like trying to understand the fundamental theorem of calculus without knowing what a function is or how to do algebra -- except in that case you can point to real-world examples about velocity and rates of flow and that kind of thing.
posted by delmoi at 7:30 AM on August 9, 2010
Others are difficult or time-consuming to solve using computers. At the level of "If you harnessed all the matter and energy in the observable universe and used them to compute the answer to this problem, it would still take billions or trillions of years."
If P=NP, then at least some of those difficult/time-consuming problems turn out to have relatively quick and easy solutions that we just don't know yet.
The problem with that explanation is that the concept of P and NP do NOT map to being "easy" or "hard". Lots of problems in P are too hard actually do, for example, while lots of problems in NP have useful heuristics that let you do them quickly (but not necessarily perfectly)
Really, in order to understand it, you have to understand the concept of a Turing machine, and what it would mean for a TM to be in multiple states at once. If you get that, then it's actually pretty simple to explain. But getting to that point takes a while.
Without that, it's kind of like trying to understand the fundamental theorem of calculus without knowing what a function is or how to do algebra -- except in that case you can point to real-world examples about velocity and rates of flow and that kind of thing.
No, you (delmoi) are wrong: Mathw isn't even wrong. P and NP are complexity classes. The Halting Problem is not a complexity problem. Putting it into P or NP is almost as ridiculous as putting jam into them.Right. At the very top you have decidability vs. undecidability. P and NP and NEXP and all that are subsets of decidable problems.
posted by delmoi at 7:30 AM on August 9, 2010
Scott Aaronson has not read all the details, being on vacation and all. But he is willing to pay $200,000 in case the proof does in fact work.
Well, he's actually betting that either the proof is wrong or that it needs some revisions (in which case he could blow off the pledge) or that the prof is right but that he could just blow it off anyway in a couple years. I mean, a blog post is hardly a contract :P
posted by delmoi at 7:41 AM on August 9, 2010
Well, he's actually betting that either the proof is wrong or that it needs some revisions (in which case he could blow off the pledge) or that the prof is right but that he could just blow it off anyway in a couple years. I mean, a blog post is hardly a contract :P
posted by delmoi at 7:41 AM on August 9, 2010
Not if you want to live in a universe that makes sense.
Well, if you could prove P = NP, then the only universe that made sense would be the one where P = NP. That's the nature of a proof.
It's not all that outlandish. After all, the set of problems solvable by a discrete finite state automata is the same as the set solvable by a non-deterministic finite state automata. The problem is you need (I think) an exponential number of discrete states compared to non-deterministic states.
posted by delmoi at 7:41 AM on August 9, 2010 [1 favorite]
Well, if you could prove P = NP, then the only universe that made sense would be the one where P = NP. That's the nature of a proof.
It's not all that outlandish. After all, the set of problems solvable by a discrete finite state automata is the same as the set solvable by a non-deterministic finite state automata. The problem is you need (I think) an exponential number of discrete states compared to non-deterministic states.
posted by delmoi at 7:41 AM on August 9, 2010 [1 favorite]
To be pedantic, P, NP, and NP-complete are classes of decision problems, meaning they only include problems with yes/no answers. TSP and any problems mentioned above for which approximations exist are optimization problems for which the goal is to find the best solution of many, and these problems are generally NP-Hard. The P=NP question impacts these as well, but they are not in P or NP themselves. Most optimization problems can be transformed into decision problems by changing "What is the best solution?" into "Does there exist a solution that costs at most k?" for some integer k.
We do have algorithms that can solve, exactly, SAT and other NP-complete problems very quickly in practice for many instances we care about. There is no approximation when a solver says, "Yes, there is a solution, and here it is." We can routinely solve instances with 100k+ variables that arise from, e.g., microprocessor verification, but any solver will often choke on randomized instances with orders of magnitude fewer variables.
posted by whatnotever at 7:51 AM on August 9, 2010 [1 favorite]
We do have algorithms that can solve, exactly, SAT and other NP-complete problems very quickly in practice for many instances we care about. There is no approximation when a solver says, "Yes, there is a solution, and here it is." We can routinely solve instances with 100k+ variables that arise from, e.g., microprocessor verification, but any solver will often choke on randomized instances with orders of magnitude fewer variables.
posted by whatnotever at 7:51 AM on August 9, 2010 [1 favorite]
It won't matter much how efficiently you can search the space of formal proofs of length K if the length of proofs of practical interest is growing like, eg, 2^N (where N == some measure of present knowledge, eg, the # of formal definitions and theorems); without at least some sense of the likely lengths of computer-verifiable formal proofs of interesting statements it's hard to feel as glib about the prospects of automated proof-hunting as, eg, Cook does in the above quote.
The fact that the lengths of proofs as written in natural language don't seem to be exhibiting exponential growth shouldn't be all that encouraging: it's long been known that for most NP problems there are polynomial-time approximations that're good to within engineering tolerances (as expressed upthread). It's entirely plausible that the algorithms employed by humans while proof-writing (and, of course, proof-checking) are in fact sloppy heuristics that're only probabilistically accurate, coupled with social practices that help ensure that faulty verdicts on important issues are eventually eliminated.
Which is the reason for skepticism about the amount of practical magic P=NP would import in terms of "creativity automation": it's entirely possible that your intuitions about realistic lengths of formal proofs of interesting statements are hugely off, in precisely the same way your intuitions about the worst-case time required to find the optimal route in the traveling salesperson problem would be "off' if you'd never heard of P or NP and you'd already discovered a polynomial-time algorithm you'd shown to always produce a result within a factor of 2 or 3 of whatever the optimal route might be.
posted by hoople at 7:56 AM on August 9, 2010
The fact that the lengths of proofs as written in natural language don't seem to be exhibiting exponential growth shouldn't be all that encouraging: it's long been known that for most NP problems there are polynomial-time approximations that're good to within engineering tolerances (as expressed upthread). It's entirely plausible that the algorithms employed by humans while proof-writing (and, of course, proof-checking) are in fact sloppy heuristics that're only probabilistically accurate, coupled with social practices that help ensure that faulty verdicts on important issues are eventually eliminated.
Which is the reason for skepticism about the amount of practical magic P=NP would import in terms of "creativity automation": it's entirely possible that your intuitions about realistic lengths of formal proofs of interesting statements are hugely off, in precisely the same way your intuitions about the worst-case time required to find the optimal route in the traveling salesperson problem would be "off' if you'd never heard of P or NP and you'd already discovered a polynomial-time algorithm you'd shown to always produce a result within a factor of 2 or 3 of whatever the optimal route might be.
posted by hoople at 7:56 AM on August 9, 2010
In polynomial time, there's no need to be afraid
In polynomial time, we let in light and we banish shade
But in our class of P we can spread a smile of joy
Put your arms around the complexity class NP, in polynomial time
DUM-dooga-DUM-dooga-DUM-dooga-DUM-doo
"Do They Know it's Polynomial Time?", the hit song from "P v NP, the Musical!"
A SONG SO CATCHY THAT IT WILL JUMP INTO YOUR OPEN MOUTH, RUN DOWN YOUR THROAT AND KICK A HOLE IN YOUR PANCREAS.
- Rolling Stone
WHY DON'T MORE MATHEMATICIANS SING THEIR PROOFS? THIS SONG JUMPED INTO MY EARHOLE, RAN AROUND MY BRAIN AND KICKED THE SHIT OUT OF MY STUDIED, YOUTHFUL CYNICISM. AND MY FACE.
- Spin
THIS SONG MADE ME JUMP INTO MY OWN ASSHOLE, TURN INSIDE OUT AND KICK THE FUCKING BEJESUS OUT OF MY OWN MOTHER WITH BLUBBERY, INSIDE-OUT LEGS.
- Kerrang!
posted by the quidnunc kid at 9:48 AM on August 9, 2010 [4 favorites]
In polynomial time, we let in light and we banish shade
But in our class of P we can spread a smile of joy
Put your arms around the complexity class NP, in polynomial time
DUM-dooga-DUM-dooga-DUM-dooga-DUM-doo
"Do They Know it's Polynomial Time?", the hit song from "P v NP, the Musical!"
A SONG SO CATCHY THAT IT WILL JUMP INTO YOUR OPEN MOUTH, RUN DOWN YOUR THROAT AND KICK A HOLE IN YOUR PANCREAS.
- Rolling Stone
WHY DON'T MORE MATHEMATICIANS SING THEIR PROOFS? THIS SONG JUMPED INTO MY EARHOLE, RAN AROUND MY BRAIN AND KICKED THE SHIT OUT OF MY STUDIED, YOUTHFUL CYNICISM. AND MY FACE.
- Spin
THIS SONG MADE ME JUMP INTO MY OWN ASSHOLE, TURN INSIDE OUT AND KICK THE FUCKING BEJESUS OUT OF MY OWN MOTHER WITH BLUBBERY, INSIDE-OUT LEGS.
- Kerrang!
posted by the quidnunc kid at 9:48 AM on August 9, 2010 [4 favorites]
I mean, a blog post is hardly a contract :P
On the contrary. He has made a perfectly valid unilateral contract. That is, a contract which is a kind of standing offer which may be accepted by performance of the terms of the contract, in this case, winning the Clay Millennium Prize for proof that P != NP. It's even in writing, so the statute of frauds is no help, despite the high dollar amount.
Of course, Aaronson can always revoke the offer any time prior to performance of the contract, although I suppose Deolalikar could raise a stink about partial performance or something.
There's nothing magical about contracts. There are very, very few formal requirements for a contract. If I were Deolalikar and I actually won the Clay Prize, I would fully expect Aaronson to cough up.
posted by jedicus at 9:59 AM on August 9, 2010
On the contrary. He has made a perfectly valid unilateral contract. That is, a contract which is a kind of standing offer which may be accepted by performance of the terms of the contract, in this case, winning the Clay Millennium Prize for proof that P != NP. It's even in writing, so the statute of frauds is no help, despite the high dollar amount.
Of course, Aaronson can always revoke the offer any time prior to performance of the contract, although I suppose Deolalikar could raise a stink about partial performance or something.
There's nothing magical about contracts. There are very, very few formal requirements for a contract. If I were Deolalikar and I actually won the Clay Prize, I would fully expect Aaronson to cough up.
posted by jedicus at 9:59 AM on August 9, 2010
Jedicus wrote: [Scott Aaronson] has made a perfectly valid unilateral contract.
I don't think so - where's the consideration? Anything that Vinay Deolalikar has done to win the prize is in the past and can't form the basis of a contract. Mind you, I suppose a court could read this as "if Vinay Deolalikar accepts the prize I will pay him ...." Is it possible to win without accepting?
Conjecture: No legal textbook is both consistent and capable of answering all legal questions.
Proof: Let every legal argument be assigned a page number in the textbook ...
posted by Joe in Australia at 10:48 AM on August 9, 2010 [2 favorites]
I don't think so - where's the consideration? Anything that Vinay Deolalikar has done to win the prize is in the past and can't form the basis of a contract. Mind you, I suppose a court could read this as "if Vinay Deolalikar accepts the prize I will pay him ...." Is it possible to win without accepting?
Conjecture: No legal textbook is both consistent and capable of answering all legal questions.
Proof: Let every legal argument be assigned a page number in the textbook ...
posted by Joe in Australia at 10:48 AM on August 9, 2010 [2 favorites]
One practical effect of P = NP would mean that public-key encryption would be on shaky footing because it depends on the fact that factoring large numbers into primes is in NP, but not P.
Can we please stop spreading this falsehood? As has been already pointed out, a problem can be solvable in polynomial time but still computationally intractable.
posted by Rhomboid at 10:55 AM on August 9, 2010
Can we please stop spreading this falsehood? As has been already pointed out, a problem can be solvable in polynomial time but still computationally intractable.
posted by Rhomboid at 10:55 AM on August 9, 2010
Anything that Vinay Deolalikar has done to win the prize is in the past
Nope.
posted by a snickering nuthatch at 10:57 AM on August 9, 2010 [1 favorite]
Nope.
Before consideration, a proposed solution must be published in a refereed mathematics publication of worldwide repute (or such other form as the SAB shall determine qualifies), and it must also have general acceptance in the mathematics community two years after.Deolalikar hasn't published this yet; he merely requested comment from other mathematicians, and it spread from there.
posted by a snickering nuthatch at 10:57 AM on August 9, 2010 [1 favorite]
Wolfdog, in your MetaChat comment you state:
I think it's a very artificial problem, which is a subjective judgement to be sure, but some problems feel like they arise naturally and would be universal problems that any mathematically-aware culture would study; others feel like they are concerned with a more arbitrary matter: they have a quirk of representation at their heart.
Could you elaborate on that? Wouldn't the fact that there is such a large class of NP-complete problems - from such diverse areas, but in a sense all essentially "the same" problem - suggest that this captures a real, fundamental property of computational complexity?
posted by ltl at 11:01 AM on August 9, 2010
I think it's a very artificial problem, which is a subjective judgement to be sure, but some problems feel like they arise naturally and would be universal problems that any mathematically-aware culture would study; others feel like they are concerned with a more arbitrary matter: they have a quirk of representation at their heart.
Could you elaborate on that? Wouldn't the fact that there is such a large class of NP-complete problems - from such diverse areas, but in a sense all essentially "the same" problem - suggest that this captures a real, fundamental property of computational complexity?
posted by ltl at 11:01 AM on August 9, 2010
delmoi -- isn't the halting problem provably NP-hard?
posted by spiderskull at 11:27 AM on August 9, 2010
posted by spiderskull at 11:27 AM on August 9, 2010
Anybody got an explanation that's not just for laymen
Lots of problems involve the relationships among the data. For instance, if you have an unordered list you have to sort, you have to compare the data to each other to see that a given element is smaller than the others. If the list is n elements long, it's easy to come up with a program to sort the list that could take up to n^2 (n*n) steps. This would be fine with 10 elements, because a modern computer can do 100 steps very quickly. But if you're trying to sort a million elements, now you have a trillion steps, and that'll slow you down. So there are cleverer sorting algorithms that take at worst n*log n steps, which will be much less than n^2, especially when you consider bigger and bigger values for n.
Sorting is a problem that's said to be in polynomial time, which is to say that an upper limit on the number of steps it takes to solve the problem in terms of the number of data involved, n, can be expressed as a polynomial. A polynomial is any expression like this:
5 + n + 3n^2 + 5n^3 + 8n^4 ...
So if you can prove that you can solve a given problem for n data in n^10000000 steps, that problem is in polynomial time, even though it would still be intractably slow to solve in the real world. The set of all problems whose solution can be found in polynomial time is called P.
There are a lot of interesting and important problems for which we don't know a method to solve them with a number of steps whose limit can be expressed as a polynomial. For instance, the "travelling salesman problem." Say you're booking travel for a salesman who has to visit 10 cities -- the order doesn't matter. Airfare being weird, the cost to travel between any two cities can't be predicted based on how close the cities are or anything. So what's the cheapest route for your travelling salesman?
There's an obvious way to solve this by trying every possibility. The number of steps for that is n! (n factorial) or 10*9*8*7*6*5*4*3*2*1. This grows very large very fast as n gets larger, and quickly becomes too many steps to be feasible on even fast computers. There's a cleverer way to solve it with a number of steps limited to at worst n^2 * 2^n. So we can describe how many steps it takes to solve it, but we can't express the number of steps as a polynomial (the 2^n disqualifies it because the exponent part would need to be a constant, even if it's an arbitrarily large constant -- if the n's in the exponent, it's not in P). So we say it can be solved in non-polynomial time, and the set of problems that can be solved in non-polynomial time is called NP.
Another problem in NP is the knapsack problem. Say you have a whole bunch of irregularly shaped boxes you want to put into shipping containers. How do you pack them so you need the minimum number of shipping containers? (This isn't the classic statement of the knapsack problem, but an equivalent that's more obviously relevant to the real world.)
So these aren't just academic questions -- lots of time and effort has gone into trying to find methods to come up with good enough solutions to these problems in a reasonable amount of time, because we don't know a way to find the best solution in a reasonable amount of time.
Now, just because a problem is in NP doesn't mean it's not in P. Maybe the things we think are clever solutions are really naive solutions and there exists a really clever solution that would show that the problem is in P.
One of the surprising and really interesting results in computer science is that the travelling salesman problem and the knapsack problem are also in a set of problems called NP-complete. That means that there exists an method that can convert any technique to solve one into a technique to solve the other, and that that method is in P. That means that if someone finds a solution to any one of these NP-complete problems that's in P, we'd be able to solve all of them in P. (There are NP problems that aren't NP-complete, so this wouldn't mean showing that all NP problems are in P.)
Now, centuries of math geniuses have tackled NP problems (problems we now know to be NP, that is -- many of the problems long predated these ideas and this nomenclature) and failed to find techniques to solve them that would prove that the problem was in P. So pretty much no one believes that there exists a solution in P to all of these problems -- we believe that P is a proper subset of NP, that is, that there exist problems that are impossible to solve in polynomial time.
But we're not sure. No one's come up with a way to actually prove that a problem absolutely couldn't be solved in P, as opposed to it just being the case that we don't know how. So for decades, this has been the great unanswered problem of computer science -- does P=NP?
If this person has proven that P is not NP, that confirms what everyone expects, and doesn't really change things much (except that people will stop trying to prove it and can move onto other things.) Now, if someone proved P=NP instead, that would be really radical and lots of heads would be exploding.
posted by Zed at 11:38 AM on August 9, 2010 [3 favorites]
Lots of problems involve the relationships among the data. For instance, if you have an unordered list you have to sort, you have to compare the data to each other to see that a given element is smaller than the others. If the list is n elements long, it's easy to come up with a program to sort the list that could take up to n^2 (n*n) steps. This would be fine with 10 elements, because a modern computer can do 100 steps very quickly. But if you're trying to sort a million elements, now you have a trillion steps, and that'll slow you down. So there are cleverer sorting algorithms that take at worst n*log n steps, which will be much less than n^2, especially when you consider bigger and bigger values for n.
Sorting is a problem that's said to be in polynomial time, which is to say that an upper limit on the number of steps it takes to solve the problem in terms of the number of data involved, n, can be expressed as a polynomial. A polynomial is any expression like this:
5 + n + 3n^2 + 5n^3 + 8n^4 ...
So if you can prove that you can solve a given problem for n data in n^10000000 steps, that problem is in polynomial time, even though it would still be intractably slow to solve in the real world. The set of all problems whose solution can be found in polynomial time is called P.
There are a lot of interesting and important problems for which we don't know a method to solve them with a number of steps whose limit can be expressed as a polynomial. For instance, the "travelling salesman problem." Say you're booking travel for a salesman who has to visit 10 cities -- the order doesn't matter. Airfare being weird, the cost to travel between any two cities can't be predicted based on how close the cities are or anything. So what's the cheapest route for your travelling salesman?
There's an obvious way to solve this by trying every possibility. The number of steps for that is n! (n factorial) or 10*9*8*7*6*5*4*3*2*1. This grows very large very fast as n gets larger, and quickly becomes too many steps to be feasible on even fast computers. There's a cleverer way to solve it with a number of steps limited to at worst n^2 * 2^n. So we can describe how many steps it takes to solve it, but we can't express the number of steps as a polynomial (the 2^n disqualifies it because the exponent part would need to be a constant, even if it's an arbitrarily large constant -- if the n's in the exponent, it's not in P). So we say it can be solved in non-polynomial time, and the set of problems that can be solved in non-polynomial time is called NP.
Another problem in NP is the knapsack problem. Say you have a whole bunch of irregularly shaped boxes you want to put into shipping containers. How do you pack them so you need the minimum number of shipping containers? (This isn't the classic statement of the knapsack problem, but an equivalent that's more obviously relevant to the real world.)
So these aren't just academic questions -- lots of time and effort has gone into trying to find methods to come up with good enough solutions to these problems in a reasonable amount of time, because we don't know a way to find the best solution in a reasonable amount of time.
Now, just because a problem is in NP doesn't mean it's not in P. Maybe the things we think are clever solutions are really naive solutions and there exists a really clever solution that would show that the problem is in P.
One of the surprising and really interesting results in computer science is that the travelling salesman problem and the knapsack problem are also in a set of problems called NP-complete. That means that there exists an method that can convert any technique to solve one into a technique to solve the other, and that that method is in P. That means that if someone finds a solution to any one of these NP-complete problems that's in P, we'd be able to solve all of them in P. (There are NP problems that aren't NP-complete, so this wouldn't mean showing that all NP problems are in P.)
Now, centuries of math geniuses have tackled NP problems (problems we now know to be NP, that is -- many of the problems long predated these ideas and this nomenclature) and failed to find techniques to solve them that would prove that the problem was in P. So pretty much no one believes that there exists a solution in P to all of these problems -- we believe that P is a proper subset of NP, that is, that there exist problems that are impossible to solve in polynomial time.
But we're not sure. No one's come up with a way to actually prove that a problem absolutely couldn't be solved in P, as opposed to it just being the case that we don't know how. So for decades, this has been the great unanswered problem of computer science -- does P=NP?
If this person has proven that P is not NP, that confirms what everyone expects, and doesn't really change things much (except that people will stop trying to prove it and can move onto other things.) Now, if someone proved P=NP instead, that would be really radical and lots of heads would be exploding.
posted by Zed at 11:38 AM on August 9, 2010 [3 favorites]
isn't the halting problem provably NP-hard?
The halting problem is NP-hard (at least as hard as the hardest problems in NP), but is not in NP itself - being undecidable you can't be sure to get an answer in any amount of time.
posted by ltl at 11:49 AM on August 9, 2010 [1 favorite]
The halting problem is NP-hard (at least as hard as the hardest problems in NP), but is not in NP itself - being undecidable you can't be sure to get an answer in any amount of time.
posted by ltl at 11:49 AM on August 9, 2010 [1 favorite]
This isn't the classic statement of the knapsack problem, but an equivalent that's more obviously relevant to the real world.
This is the problem I have with all of these explanations -- they make it out to seem as if NP problems are just too hard to be tackled currently, and if someone could somehow finally figure out P =? NP then we could start to come to terms with how to deal with them. But that omits the fact that we've found pretty good algorithms for a lot of these NP problems like the traveling salesman, solvers that produce results 'good enough' in most cases. What they can't do is find the optimal solution, but in the real world that just doesn't matter; if it costs $10 to get to 99% of optimal and $1,000,000 to get to 100% optimal, which are you going to pick? From the theory side of things this is of course a major topic, but I just don't see that it does anyone any good to try to frame this as if it would have these vast practical implications.
posted by Rhomboid at 12:24 PM on August 9, 2010
This is the problem I have with all of these explanations -- they make it out to seem as if NP problems are just too hard to be tackled currently, and if someone could somehow finally figure out P =? NP then we could start to come to terms with how to deal with them. But that omits the fact that we've found pretty good algorithms for a lot of these NP problems like the traveling salesman, solvers that produce results 'good enough' in most cases. What they can't do is find the optimal solution, but in the real world that just doesn't matter; if it costs $10 to get to 99% of optimal and $1,000,000 to get to 100% optimal, which are you going to pick? From the theory side of things this is of course a major topic, but I just don't see that it does anyone any good to try to frame this as if it would have these vast practical implications.
posted by Rhomboid at 12:24 PM on August 9, 2010
You saw where I said that this proof wouldn't change things much, right? And mentioned the difference between good enough and best? And that something could be in P but still be infeasibly difficult to calculate? I'm not seeing that your objections weren't already addressed.
posted by Zed at 12:32 PM on August 9, 2010
posted by Zed at 12:32 PM on August 9, 2010
Zed: So we say it can be solved in non-polynomial time, and the set of problems that can be solved in non-polynomial time is called NP.
NP is not non-polynomial time, but non-deterministic polynomial, which means that if someone provides you with an answer, you can check the answer for correctness in polynomial time. In the traveling salesman problem, the decision problem is the question "Is there a route with length < k?" Given a yes-answer and a route, it is easy to check whether the route is valid (shorter than length k and visits all cities).
That means that if someone finds a solution to any one of these NP-complete problems that's in P, we'd be able to solve all of them in P. (There are NP problems that aren't NP-complete, so this wouldn't mean showing that all NP problems are in P.)
For a problem to be NP-complete, it has to be in NP and be NP-hard, which states that any problem in NP can be reduced in polynomial time to that problem. So, if one of these NP-complete problems is shown to be in P, we can solve all NP problems, showing P=NP. The NP-complete problems are the hardest problems in NP, so, if they are "easy", all the less hard problems are easy, too.
posted by ltl at 12:38 PM on August 9, 2010
NP is not non-polynomial time, but non-deterministic polynomial, which means that if someone provides you with an answer, you can check the answer for correctness in polynomial time. In the traveling salesman problem, the decision problem is the question "Is there a route with length < k?" Given a yes-answer and a route, it is easy to check whether the route is valid (shorter than length k and visits all cities).
That means that if someone finds a solution to any one of these NP-complete problems that's in P, we'd be able to solve all of them in P. (There are NP problems that aren't NP-complete, so this wouldn't mean showing that all NP problems are in P.)
For a problem to be NP-complete, it has to be in NP and be NP-hard, which states that any problem in NP can be reduced in polynomial time to that problem. So, if one of these NP-complete problems is shown to be in P, we can solve all NP problems, showing P=NP. The NP-complete problems are the hardest problems in NP, so, if they are "easy", all the less hard problems are easy, too.
posted by ltl at 12:38 PM on August 9, 2010
That's a fair cop -- ltl's objections are correct and I was wrong on those points.
posted by Zed at 12:51 PM on August 9, 2010 [1 favorite]
posted by Zed at 12:51 PM on August 9, 2010 [1 favorite]
For instance, the "travelling salesman problem." Say you're booking travel for a salesman who has to visit 10 cities -- the order doesn't matter. Airfare being weird, the cost to travel between any two cities can't be predicted based on how close the cities are or anything. So what's the cheapest route for your travelling salesman?
I'm confused by this part of Zed's explanation. Based on some of the other explanations up-thread and from what I've gleaned from other sources, I thought I had a good handle, at least, on what the Traveling Salesman problem was about. But Zed's clarification here seems to conflict with that previous understanding, so if anyone can help me sort out which is correct, I'd appreciate it.
My previous understanding was that the problem concerned devising an algorithm capable of determining the shortest possible route that visits each location only once starting from any arbitrary point in a set of location points {a, b, c, d, e} for which the pairwise distances are known.
But if, as Zed characterizes it, the problem also has something to do with the cost of airfare for any given trip between two points and that cost has only an arbitrary relation to the distances traveled on each leg of the trip, then my previous understanding was an oversimplification of the problem. Zed's summary seems to differ from some other explanations I've seen in this one respect.
So was my previous understanding correct? Or is Zed's explanation correct?
posted by saulgoodman at 1:10 PM on August 9, 2010
I'm confused by this part of Zed's explanation. Based on some of the other explanations up-thread and from what I've gleaned from other sources, I thought I had a good handle, at least, on what the Traveling Salesman problem was about. But Zed's clarification here seems to conflict with that previous understanding, so if anyone can help me sort out which is correct, I'd appreciate it.
My previous understanding was that the problem concerned devising an algorithm capable of determining the shortest possible route that visits each location only once starting from any arbitrary point in a set of location points {a, b, c, d, e} for which the pairwise distances are known.
But if, as Zed characterizes it, the problem also has something to do with the cost of airfare for any given trip between two points and that cost has only an arbitrary relation to the distances traveled on each leg of the trip, then my previous understanding was an oversimplification of the problem. Zed's summary seems to differ from some other explanations I've seen in this one respect.
So was my previous understanding correct? Or is Zed's explanation correct?
posted by saulgoodman at 1:10 PM on August 9, 2010
It's the same problem -- you can look at the numbers describing the relationships between the cities as meaning distance and you're looking for the shortest route, or you can look at the numbers as meaning cost and you're looking for the cheapest route. (My description was incomplete in that I left out the visit each city exactly once part.) As with the shipping container example, I was going for a more obviously real-world version of the problem.
posted by Zed at 1:18 PM on August 9, 2010
posted by Zed at 1:18 PM on August 9, 2010
Thanks Zed. Makes sense.
posted by saulgoodman at 1:19 PM on August 9, 2010
posted by saulgoodman at 1:19 PM on August 9, 2010
Love the comment, Wolfdog, but your saying that P ?= NP is "artificial" makes me feel like the Pope would if you told him that God was artificial.
Given that the actual physical universe could be said to be generally capable of solving only BQP problems, I feel that complexity classes are extremely fundamental.
posted by Earl the Polliwog at 1:30 PM on August 9, 2010
Given that the actual physical universe could be said to be generally capable of solving only BQP problems, I feel that complexity classes are extremely fundamental.
posted by Earl the Polliwog at 1:30 PM on August 9, 2010
On the contrary. He has made a perfectly valid unilateral contract. That is, a contract which is a kind of standing offer which may be accepted by performance of the terms of the contract, in this case, winning the Clay Millennium Prize for proof that P != NP. It's even in writing, so the statute of frauds is no help, despite the high dollar amount.Interesting. There was a thread the other day about a lawyer who offered a million dollars on dateline if anyone could prove that someone could get from an airport to a location (where his client was aledged to have killed someone) in 15 minutes, or something like that. A law student tried it and was able to do it, then sued for the money. So I guess that's a good point. Still, I'm sure Aaronson doesn't really think he'll really have to pay if the guy's proof turns out to be correct. There are a whole much of reasons why he might not have too.
--
delmoi -- isn't the halting problem provably NP-hard?
Absolutly not. Every NP-hard problem is solvable in a finite (but very long) amount of time. So no. In fact, NP-hard problems on small data sizes are doable in real time
So for example, an NP-hard problem with,say, 3-5 items can still be solved in a few seconds.
From wikipedia:
An example of an NP-hard problem is the decision subset sum problem, which is this: given a set of integers, does any non-empty subset of them add up to zero? That is a yes/no question, and happens to be NP-complete. Another example of an NP-hard problem is the optimization problem of finding the least-cost route through all nodes of a weighted graph. This is commonly known as the Traveling Salesman Problem.So, for example if you have the integers '3, -5, 8, 2, -6' are there any combinations that add up to zero? Obviously there are. If you took any list of a handful of integers, you should always be able to do that subset sum problem pretty easily. It's only when you get up to large set sizes that it gets difficult. But you would always eventually get an answer, either yes or no.
The halting problem, on the other hand may never end up giving you an answer.
Maybe this confusion between NP and undecidability is why people imbue a proof of P = NP with so much portent. But the fact that decidable and undecidable problems are not equal was proven a long time ago.
The halting problem is NP-hard (at least as hard as the hardest problems in NP), but is not in NP itself - being undecidable you can't be sure to get an answer in any amount of time.Uh, no. if you can't get an answer in a limited amount of time, then the problem is NOT NP-Hard. The definition of an NP hard problem is one that a non deterministic Turing machine" can solve in polynomial time. NP stands for "nondeterministic polynomial", not "Not polynomial"
---
to summarize: All problems in NP can be solved in a finite amount of time. They are all decidable And the halting problem is undecidable which means you may eventually get a yes, but you may never get a 'no'.
NP is not the set of the 'hardest' problems, there are other harder problem types, including NEXP, which takes an exponential amount of time even on a non-deterministic Turing machine.
posted by delmoi at 2:51 PM on August 9, 2010
It's the same problem -- you can look at the numbers describing the relationships between the cities as meaning distance and you're looking for the shortest route, or you can look at the numbers as meaning cost and you're looking for the cheapest route.
They're not quite the same: literal distances have to obey the triangle inequality, while costs do not. Both cases are still NP complete, but I believe the former (metric distances) has better approximation algorithms.
posted by Pyry at 2:58 PM on August 9, 2010
They're not quite the same: literal distances have to obey the triangle inequality, while costs do not. Both cases are still NP complete, but I believe the former (metric distances) has better approximation algorithms.
posted by Pyry at 2:58 PM on August 9, 2010
So was my previous understanding correct? Or is Zed's explanation correct?
Your previous understanding is fine. Zed's explanation seems to be for the non-Euclidean case, i.e., distances between cities don't necessarily "make sense". However, the Euclidean case is still NP-complete.
See Wikipedia
posted by qxntpqbbbqxl at 2:58 PM on August 9, 2010
Your previous understanding is fine. Zed's explanation seems to be for the non-Euclidean case, i.e., distances between cities don't necessarily "make sense". However, the Euclidean case is still NP-complete.
See Wikipedia
posted by qxntpqbbbqxl at 2:58 PM on August 9, 2010
delmoi, ltl is right. In order to be NP-hard you do not have to be in the class NP. Your definition is of a problem that is in the class NP.
A problem is NP-hard if any problem in NP can be reduced to it in polynomial time.
A problem is NP-complete if it is in NP and is also NP-hard.
posted by louigi at 3:01 PM on August 9, 2010
A problem is NP-hard if any problem in NP can be reduced to it in polynomial time.
A problem is NP-complete if it is in NP and is also NP-hard.
posted by louigi at 3:01 PM on August 9, 2010
ltl: you can deflate a lot of the magic around P=NP by pointing out that you might as well call the NP-complete problems the "efficiently-equivalent-to-SAT" problems.
Given the generality of SAT it's not surprising that most decision problems have straightforward reductions to SAT, and given that fact an obvious next step is to restrict your attention to those problems whose reductions to SAT have tractable length (in terms of their length in their native form).
Having made that step there's a little surprise in the remainder of the construction -- it is initially surprising that you can efficiently reduce SAT to seemingly-less-general problems in an efficient way -- but on the other hand simple boolean circuits (like simple gates, adders, etc.) are also surprisingly easy to embed in other systems (conway's life, mechanical apparati, etc.) and once you've seen enough of the tricks that can be used a lot of the magic disappears as well.
This is a bit of a reductionistic and jerky way to look at it, to be sure, but it can be easy to lose sight of just how general a problem SAT is (on the one hand) but also how easy it is to embed boolean circuitry (and similar) into various settings.
Earl the Polliwog: can't speak for Wolfdog but the sense of artificiality is defensible.
What would seem completely natural is something like: we have a robust way of defining "systems" and "order" (where "order" would in general be problem-specific, for "problem" in the sense used in computational complexity theory). We then have some fundamental speed limit or unit cost involved in taking a system from a "disorderly" state to an "orderly" state, with the speed limit or unit cost expressed in something like time or energy or entropy, etc., per quantum of disorder eliminated or some such. You would then, hopefully, be able to reconstruct the existing formulation of the limits of polynomial time algorithms as a byproduct of that more fundamental speed limit or unit cost.
As-is it seems like there's perhaps a very deep thing underlying P vs. NP but that the characterization of that thing in terms of polynomial-time algorithms -- while seemingly adequate -- isn't perhaps the most insightful or natural characterization.
posted by hoople at 3:38 PM on August 9, 2010
Given the generality of SAT it's not surprising that most decision problems have straightforward reductions to SAT, and given that fact an obvious next step is to restrict your attention to those problems whose reductions to SAT have tractable length (in terms of their length in their native form).
Having made that step there's a little surprise in the remainder of the construction -- it is initially surprising that you can efficiently reduce SAT to seemingly-less-general problems in an efficient way -- but on the other hand simple boolean circuits (like simple gates, adders, etc.) are also surprisingly easy to embed in other systems (conway's life, mechanical apparati, etc.) and once you've seen enough of the tricks that can be used a lot of the magic disappears as well.
This is a bit of a reductionistic and jerky way to look at it, to be sure, but it can be easy to lose sight of just how general a problem SAT is (on the one hand) but also how easy it is to embed boolean circuitry (and similar) into various settings.
Earl the Polliwog: can't speak for Wolfdog but the sense of artificiality is defensible.
What would seem completely natural is something like: we have a robust way of defining "systems" and "order" (where "order" would in general be problem-specific, for "problem" in the sense used in computational complexity theory). We then have some fundamental speed limit or unit cost involved in taking a system from a "disorderly" state to an "orderly" state, with the speed limit or unit cost expressed in something like time or energy or entropy, etc., per quantum of disorder eliminated or some such. You would then, hopefully, be able to reconstruct the existing formulation of the limits of polynomial time algorithms as a byproduct of that more fundamental speed limit or unit cost.
As-is it seems like there's perhaps a very deep thing underlying P vs. NP but that the characterization of that thing in terms of polynomial-time algorithms -- while seemingly adequate -- isn't perhaps the most insightful or natural characterization.
posted by hoople at 3:38 PM on August 9, 2010
I'm excited by this, but I wish fields would be better about unifying terms. In philosophy, P!=NP is a clear tautology.
posted by Navelgazer at 11:56 PM on August 9, 2010
posted by Navelgazer at 11:56 PM on August 9, 2010
This is a blog post trying to gather the possible issues in the proof that have been raised in first reviews.
posted by ltl at 12:46 AM on August 10, 2010
posted by ltl at 12:46 AM on August 10, 2010
This is a comment in the previously posted blog about an apparently unfixable problem in the proof.
posted by Obscure Reference at 3:42 PM on August 10, 2010
posted by Obscure Reference at 3:42 PM on August 10, 2010
OR, that comment is retracted a little further down.
posted by gleuschk at 6:45 PM on August 11, 2010
posted by gleuschk at 6:45 PM on August 11, 2010
- Scott Aaronson comments on the ethics of his $200,000 bet that the proof is not correct.
- A Wiki tracking the various issues, the updates by Vinay Deolalikar to the proof and the media coverage.
- At Prof. Lipton's blog, with discussion of the issues in the comments: Update on Deolalikar's Proof that P≠NP and Deolalikar Responds To Issues About His P≠NP Proof .
- A beautiful sausage.
Tide turns against million-dollar maths proof.
posted by Obscure Reference at 7:43 AM on August 14, 2010
posted by Obscure Reference at 7:43 AM on August 14, 2010
I'm asking this for my friend because he's too embarrassed to ask himself. Why is it so hard to find a problem in NP that we can be sure isn't in P?
Also, he has a question about girls. How do you know when they like you?
posted by Joe in Australia at 8:43 AM on August 14, 2010
Also, he has a question about girls. How do you know when they like you?
posted by Joe in Australia at 8:43 AM on August 14, 2010
Because the search space for algorithms is immeasurably large. Even if we've searched through a 100,000,000 possible ways to solve the problem and have come up short, we can't be certain that the next one or the next thousandth or the next trillionth we check won't solve it.
posted by empath at 8:46 AM on August 14, 2010
posted by empath at 8:46 AM on August 14, 2010
So it's possible that there is a polynomial-time answer to, say, the Traveling Salesman Problem, but we just haven't found it?
posted by Joe in Australia at 9:12 AM on August 14, 2010
posted by Joe in Australia at 9:12 AM on August 14, 2010
Good question, someone ought to look into that.
posted by Wolfdog at 9:29 AM on August 14, 2010 [2 favorites]
posted by Wolfdog at 9:29 AM on August 14, 2010 [2 favorites]
Ever wonder what would happen if you posted P vs NP as a coding job on one of those overseas contractor hiring sites? Yeah, it's about as bad as you think with people bidding $300 and plenty of broken English. On the one hand I kind of feel bad for making fun of these guys for not groking the requirement that the program run in polynomial time or not even groking the nature of the problem at all, but on the other hand it's hard to have sympathy for people that claim to practice an art without being at all familiar with some of the theoretical foundations of that art. It would almost be like a machinist replying to a want ad looking for someone to build them a perpetual motion machine.
posted by Rhomboid at 3:34 PM on August 18, 2010 [1 favorite]
posted by Rhomboid at 3:34 PM on August 18, 2010 [1 favorite]
« Older Doing the Reactionary | Think Pink. Newer »
This thread has been archived and is closed to new comments
posted by twoleftfeet at 12:10 AM on August 9, 2010