+- Southperry.net (https://www.southperry.net)
+-- Forum: Social (https://www.southperry.net/forumdisplay.php?fid=14)
+--- Forum: Rubik's Cube (https://www.southperry.net/forumdisplay.php?fid=58)
+--- Thread: Paper claims to prove P != NP (/showthread.php?tid=29000)
Paper claims to prove P != NP - Spaz - 2010-08-14
On August 6th, Vinay Deolalikar distributed a paper claiming to prove P != NP
Wikipedia has a good article on the P = NP problem. Basically
Wikipedia Wrote:In essence, the question P = NP? asks:
Suppose that solutions to a problem can be verified quickly. Then, can the solutions themselves also be computed quickly?
The theoretical notion of quick used here is that of an algorithm that runs in polynomial time. The general class of questions for which some algorithm can provide an answer in polynomial time is called "class P" or just "P".
For some questions, there is no known way to find an answer quickly, but if one is provided with information showing what the answer is, it may be possible to verify the answer quickly. The class questions for which an answer can be verified in polynomial time is called NP.
Consider the subset sum problem, an example of a problem which is easy to verify but whose answer is suspected to be theoretically difficult to compute. Given a set of integers, does some nonempty subset of them sum to 0? For instance, does a subset of the set {−2, −3, 15, 14, 7, −10} add up to 0? The answer "yes, because {−2, −3, −10, 15} add up to zero" can be quickly verified with three additions. However, finding such a subset in the first place could take more time, hence this problem is in NP.
An answer to the P = NP question would determine whether problems like the subset-sum problem that can be verified in polynomial time can also be solved in polynomial time. If it turned out that P does not equal NP, it would mean that some NP problems are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.
The paper is obviously attracting a lot of scrutiny. Some people claim to have found flaws in the proof.
This is huge if the proof is correct. The problem of whether P = NP is the biggest unsolved problem in computer science and is a Millennium Prize problem. If the proof is correct, the Clay Mathematics Institute owes the guy a million dollars.
Paper claims to prove P != NP - Takebacker - 2010-08-14
Does it change anything if it's right?
Paper claims to prove P != NP - Cactuar - 2010-08-14
Takebacker Wrote:Does it change anything if it's right?
It means every encryption can be solved in a determinable amount of time.
Paper claims to prove P != NP - Spaz - 2010-08-14
Takebacker Wrote:Does it change anything if it's right?Not really. P != NP is what most computer scientists have long believed to be true because in 40 years no one has found a fast solution to any NP problem. So basically it would just be formal proof of what is already believed to be true.
It would be hard proof that certain encryption algorithms are unbreakable.
Cactuar, I think you have it backwards.
Winning slashdot comment:
Quote:We'll know that P != NP if it takes us less time to verify the proof as it took him to generate it.
Paper claims to prove P != NP - Cactuar - 2010-08-14
Spaz Wrote:Cactuar, I think you have it backwards.
Yeah. I read the topic as "Proof that P = NP." My bad.
Paper claims to prove P != NP - Noah - 2010-08-14
I'm afraid that the proof (currently! He updates the proof every now and then) doesn't work for 2SAT. If it doesn't work for 2SAT, then it sounds improbable that this will be solved through this proof.
It has no practical effect though, apart from writing some notes about NP in university textbooks.
Noah
Paper claims to prove P != NP - Kortestanov - 2010-08-16
Cactuar Wrote:It means every encryption can be solved in a determinable amount of time.P doesn't mean determinable amount of time. P means the time complexity of the algorithm would be polynomial on any deterministic turing machine.