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
“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.
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)
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)
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.while(int i = 0 < 10){i = (i+1) % 9;}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)
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.
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.
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.
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.
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 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"
« Older "Don't go Left/But be polite/Move to the Righ... | The Independant's 2010 Pink Li... Newer »
This thread has been archived and is closed to new comments
posted by twoleftfeet at 12:10 AM on August 9, 2010