Slashdot Mirror

← Back to Stories (view on slashdot.org)

No P = NP Proof After All

Posted by CmdrTaco on from the big-o-my-god dept.

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

3 of 318 comments (clear)

  1. Mistake in Summary by Haedrian · · Score: 4, Informative

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

    1. Re:Mistake in Summary by domulys · · Score: 4, Informative

      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.

  2. Re:Let me ask a "stupid" question by kelemvor4 · · Score: 4, Informative

    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.