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..."

Comments

Mistake in Summary

[Haedrian]

"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.

Re:Mistake in Summary

[domulys]

The word you're looking for is intractable:

http://en.wikipedia.org/wiki/Computational_complexity_theory#Intractability

The term "infeasible" w.r.t. constraint satisfaction problems (like 3-SAT) does not refer to the difficultly of the problem, but rather its result. For instance, an easy SAT problem with no solution would be infeasible.

Re:Let me ask a "stupid" question

[NdrU42]

(since crypto relies on N being a very large number, large enough to where it's not worth it to spend NP time breaking the encryption, but where P allows for realtime encryption/decryption.)

If by "N" you mean the "N" in "NP", then I think you've got it wrong. 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.

Re:Let me ask a "stupid" question

[kelemvor4]

This. How is GP even a real question? Could we have given your 89yo grand father a "sincere 'down-to-earth' answer" to the "what is quantum theory" question? Oh, he did not understand? Never mind quantum cryptography, then. Never mind research into prime factorisation.

Seriously, what is with people thinking "if I can not understand it fuck it" these days? How arrogant have we become?

There's a whole profession dedicated to decoding things like this and summarizing them into easy to understand tidbits we call "NEWS ARTICLES". There are probably very few people who understand the science being done at CERN yet a large number of average joes have some idea what is being researched there due to this mysterious "NEWS ARTICLE" phenomenon. Hey, I think I'll go check out one of these "NEWS ARTICLE" websites.. perhaps slashdot.org. You may want to rethink things if you think the person you replied to is the person who's being arrogant in this discussion.

Re:This will NO break any encryption algorithms...

[canajin56]

Prime factorization is in NP (proof is just about as trivial as they come) and therefore if P=NP, there must exist a polynomial time algorithm for prime factorization. Who gives a fuck if factorization is NP complete or not, that doesn't matter in the slightest. I suggest you learn what NP complete means, as a start.