Slashdot Mirror
No P = NP Proof After All
00_NOP writes "Internet commerce seems safe for now as Russian computer scientist Vladimir Romanov has conceded that his previously published solution to the '3 SAT' problem of boolean algebra does not work. If his solution did work it would have shown that many problems thought to be unsolvable with conventional computers — including decrypting your HTTPS encoded credit card number — would have been solvable in polynominal time. Romanov, who is very far from the sort of crank who normally claims to have proved P = NP or the opposite, is not giving up though..."
That's like the worst article ... ever. No information at all.
Everyone knows that Poo =/= No Poo.
Either it's covered with poo or it's devoid of poo.
We should concentrate on figuring out whether God likes poutine.
How does the solving of problems like these really help the world? I would like a sincere 'down-to-earth' answer that my 89 year old grandfather can understand and therefore be in position to donate to the effort of solving such problems.
Thanks.
Sounds like this guy needs needs some P.
OP || NP > - P
Now we get to wade through the "I can prove it when N=1" posts all over again.
Proof = No Proof
Seriously. If people want to prove or disprove a theory, let them be... it doesn't have to be pejorative. The sciences require the ability to explore (even in areas deemed 'pseudo science') to truly test the answer space and find the global minimum.
"unsolvable with conventional computers"
They're not unsolvable, they're infeasible. There's an important difference.
You can solve TSP for 1 million cities if you're willing to wait a few billion years, but the fact that you're waiting a few billion years makes it infeasible.
Either
N=1
or
P=0
Actually, he's very much the classic style of crank. Instead of giving us a formal proof, his proof is a proof by example consisting of a great deal of code that has to be scrutinized by hand for conceptual errors. It works fine on his test cases of course; so therefore to him his "proof" is "correct."
> How does the solving of problems like these really help the world? I would like a sincere 'down-to-earth' answer that my 89 year old grandfather can understand and therefore be in position to donate to the effort of solving such problems.
Here's one for your grandfather then. When you bank online, you go onto a secure web site. The information you send to your bank is digitally encrypted. A bunch of mathematicians have demonstrated that the 3SAT problem is just as hard, or harder, as breaking the encryption that keeps your grandfather's bank info secure. So, if Romanov turned out to be right somehow, it wouldn't be safe for your granddad to bank using computers anymore, because Romanov would have indirectly created an algorithm that could be used to crack the encryption in a reasonable amount of time.
Other Slashdotters will come up with plenty of other examples why 3SAT is important.
So, it has been proved that it is not possible to prove something we may or may not be able to prove?
Not to bust anyone's bubble, but the factoring problem is actually not known to be NP completely and evidence points to the fact that it is no, since if it could be shown to be then this would prove that NP=Co-NP. Similarly, the discrete logarithm problem is also not known to be NP-complete. Therefore, public key cryptosystems should be fine.
Symmetric key cryptosystems such as 3-DES and AES should also be fine. They aren't known to be NP complete problems, and in fact there are no theoretical guarantees about their security at all. They just seem to create messages that are difficult to decrypt given our current cryptoanalytic abilities. In fact, there are NO known NP-complete crypto schemes around today.
TL;DR - No encryption schemes will be broken if it is proved that P=NP.
his errors are obvious really, anyone with a college degree who browses his would could have caught them easily.
Is this the same Russian Romanov that nuked Chicago and had that dreadnought fleet in that historical Red Alert 2? If so, I'm calling in Tanya.
A 3-sentence comment in a blog is converted into a 4-sentence blog post by someone else, and that is converted into a news story by Slashdot?
Not to burst anyone's bubble, but the factoring problem is actually not known to be NP completely and evidence points to the fact that it is not, since if it could be shown to be then this would prove that NP=Co-NP. This would be a surprising result since it would prove that the graph isomorphism problem is in NP. Similarly, the discrete logarithm problem is also not known to be NP-complete. Therefore, public key cryptosystems should be fine. Symmetric key cryptosystems such as 3-DES and AES should also be fine. They aren't known to be NP complete problems, and in fact there are no theoretical guarantees about their security at all. They just seem to create messages that are difficult to decrypt given our current cryptoanalytic abilities. In fact, there are NO known NP-complete crypto schemes around today. TL;DR - No encryption schemes will be broken if it is proved that P=NP
AES-256 is known to be in complexity class P, in fact it's in complexity class C, problems that can be solved in constant time. The idea that problems solvable in polynomial time are easy and those that aren't are hard is not true for problems of practical size. See http://world.std.com/~reinhold/p=np.txt
Let's just do a bit of algebra..
State the problem.
P = NP
I'm solving for N, so lets swap the equation around.
NP = P
Let's isolate the N.
N = P/P
Simplify the division.
N = 1
Eureka! I've simplified the "Does P = NP?" problem down to just "Does N = 1?".
On the same blog, actually:
http://cartesianproduct.wordpress.com/2010/12/29/what-if-p-np/
morcego
TL;DR - No encryption schemes will be broken if it is proved that P=NP.
Also there is no guarantee that a P=NP solution must be feasible. There may exist a polynomial solution to cracking AES, BUT that specific problem may result in polynomial coefficients that are so unimaginably large as to require lots of Knuths uparrow notation to express numerically, making it a meaningless victory.
Sample dialogue: "The good news is its poly, in fact not only poly, but linear, in fact not only linear but coefficient of one, so if we double the key length then we only double the search time. The bad news is we're talking about doubling a trillion times the lifetime of the universe assuming every atom in the universe did an op every Planck time. Other than that, no problemo, because P = NP."
"Science flies us to the moon. Religion flies us into buildings." - Victor Stenger
Every story under Slashdot lately has some asshole griping about the inadequacy of the story subject.
Hey, adequacy police assholes: don't take it so fucking seriously. And stop taking yourselves so fucking seriously. This is a place to hang out and discuss random topics of nerd interest. That's it. That's all this place is. We're not compiling the text to Bible 2.0. Yet you attack the adequacy of story subjects as if you were some sort of religious fundamentalist and we were insulting your religion.
Get the fuck over yourselves.
intellectual property law is philosophically incoherent. it is your moral duty to ignore it or sabotage it
Just because something is solvable in polynomial time does not mean it's solvable quickly. For example, the best solution could be n^123471239481872349 time. This would be infeasible for all n>=2.
I'm glad that Vlad hasn't given up.
Factoring and discrete logarithm are in NP, but not known to be NP-complete. That means they are definitely polynomial time if P = NP, and might be broken even without showing P = NP.
Not to bust anyone's bubble, but the factoring problem is actually not known to be NP completely and evidence points to the fact that it is no, since if it could be shown to be then this would prove that NP=Co-NP. Similarly, the discrete logarithm problem is also not known to be NP-complete. Therefore, public key cryptosystems should be fine.
TL;DR - No encryption schemes will be broken if it is proved that P=NP.
You got that wrong. If P=NP, then NP=Co-NP, so your public key cryptosystems are broken. (Also, if P=NP, all problems in P are NP complete)
Of course I also got the P NEQ NP one just in case...
--
Marc A. Lepage
Software Developer
Oh that's alright, we'll just make a machine that includes the AES cracking algorithm as a machine instruction. Then the time complexity of cracking n bits of AES is only 2n+1 clock cycles!
P=NP when N=1. There I solved it, where's my $1 million?
Last night it was quite clear that NP is P.
3-SAT is in NP, so it's solvable by definition in polynomial time – on a non-deterministic turing machine. It's whether it's solvable in polynomial time specifically on a deterministic turing machine that defines whether it's in P.
You can solve TSP for 1 million cities if you're willing to wait a few billion years,
The TSP is quite solvable. There are pathological cases that are NP-hard, but most cases aren't. The classic Bell Labs stochastic solution for the TSP (break path into 3 sections at random, reassemble in shortest way, repeat until no improvement for a while) will converge on the shortest path most of the time, and a near-shortest path almost all the time. This approach requires something like O(N log N) time.
There are many hard problems like that. Linear programming has the same property. It's unknown whether factoring has that property.
My old CS professor called NP "non-polynomial" time so NP=P meaning something like being able to reduced 2^N computations to N^power computation.
Wow, your CS prof messed up big time in explaining that. The question whether NP is polynomial or not is one of the biggest freaking open questions in CS.
The whole "speedy solution" vs. "speedy check" way of describing P vs. NP is not the one I prefer, because it is a bit derivative. The root of the NP class comes from a concept in automata theory called a Nondeterministic Turing Machine. The simple explanation of this is that it's a mathematical model of an infinitely parallel computer, in the sense that it can perform any finite number of computations in parallel (there's no upper bound on the number of threads, and these threads are truly parallel).
NP is the class of problems that such a computer could solve in polynomial time. Since such a computer can spawn a separate thread for each candidate answer, the alternative statement of this is that it's the problems for which proposed solutions can be checked in deterministic polynomial time—since the generic nondeterministic algorithm for solving any problem is "try all candidate solutions in parallel, and pick one that checks out."
In other words: if P=NP, that means that there is a relatively efficient single-threaded simulation of an infinitely parallel computer.
Are you adequate?
The N is not a number, it stands for "non-deterministic", meaning that problems in NP can by solved by non-deterministic turing machine (which we don't know how to build) in polynomial time (the "P" stands for polynomial). Problems in P can be solved in polynomial time by a regular (deterministic) turing machine.
And the simpler way of explaining this (not guaranteed to be 100% accurate) is the following: a non-deterministic Turing Machine is basically an infinitely parallel computer, in the sense that it can spawn any finite number of truly parallel threads at no cost. An NP problem is one that you can solve in polynomial time in such an infinitely parallel machine; the general nondeterministic algorithm is just to spawn one thread for each candidate solution, have each thread simply check whether the candidate passes, and return a successful try.
If P=NP, what that means is that there is an efficient single-threaded simulation of an infinitely parallel computer.
Are you adequate?
You just got here, how do you know what it's for?
N = 1
Depends. It might be that the best algorithm for breaking our public key cryptosystems is O(n^1000). That's polynomial, but still safe.
The Tao of math: The numbers you can count are not the real numbers.
Not to bust anyone's bubble, but the factoring problem is actually not known to be NP completely and evidence points to the fact that it is no[t]
Not to burst your bubble, but while factoring isn't believed to be NP-complete, it is definitely in NP. This means that it is actually easier to solve than NP-complete problems.
More evidence that factoring is not NP-complete is that there exists an algorithm called general number field sieve that has sub-exponential running time. If factoring were NP-complete, it would mean that all NP-complete algorithms could be solved in sub-exponential time, which is considered unlikely. Factoring is probably easier than NP-complete problems.
In fact, it seems that the current public-key algorithms are all apparently easier to solve than NP-complete problems.
"Screw Sun, cross-platform will never work. Let's move on and steal the Java language." - Visual J++ Product Manager