Catch up on stories from the past week (and beyond) at the Slashdot story archive

 


Forgot your password?
Close
typodupeerror
×
Math Science

No P = NP Proof After All 318

Posted by CmdrTaco 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..."
This discussion has been archived. No new comments can be posted.

No P = NP Proof After All More

No P = NP Proof After All

Comments Filter:

  • A better heading (Score:3, Funny)

    by Anonymous Coward on Monday February 28, 2011 @09:50AM (#35337680)

    Proof = No Proof

  • Mistake in Summary (Score:5, Informative)

    by Haedrian ( 1676506 ) on Monday February 28, 2011 @10:03AM (#35337818)

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

    • I read it as "unsolvable" in the sense that computers in the real world cannot currently solve them with current algorithms, instead of unsolvable in the abstract sense of, for instance, a Turing machine with unlimited steps and tape solving them in a finite number of steps. But, I agree that the wording is imprecise.
      • They can be solved, it just takes a long time. So current algorithms are just too inefficient. There are efficient heuristic algorithms, but they will only give you a good answer, not necessarily the best one, but for many problems, good is often good enough.

      • Re: (Score:2)

        by danlip ( 737336 )

        Computers in the real world (by which I assume you mean personal computers) can easily solve TSP for 10 cities. Maybe even 100. The threshold for feasibility of any NP problem depends on the size of the input. At some point it is feasible for all computers, and at some point it is not feasible even for the biggest computers.

        A more precise definition would be "Turing-computable". TSP is computable. The halting problem is not.

        • Yes, the size of the problem is of course paramount, even for polynomial time algorithms. My point (which I didn't express perfectly) was that the GP took "unsolvable" to mean "not Turing computable", while I just took it to mean "the hardware will probably break or the programmer will die long before the thing finishes", i.e. the problem is practically (though not abstractly) unsolvable.

      • So if we started doing the calculations today, one day someone would have a better computer or algorithm that would surpass all the work we'd done over years. Not really an incentive to getting on that one! Not to mention the code would have gone through countless hardware and software changes, power loss, etc. over a billion years. I figure someone 10000 years from now would go "hey, what's this computer for?" and the other guy would be like "no idea.. just unplug it".

    • Re:Mistake in Summary (Score:4, Informative)

      by domulys ( 1431537 ) on Monday February 28, 2011 @10:54AM (#35338398)
      The word you're looking for is intractable:

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

      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.

      • I should also point out that some so-called "intractable" problems can be solved fairly quickly. Many 3-SAT problems can be quickly solved by algorithms [wikipedia.org] such as DPLL or WalkSAT. It's just that solving a 3-SAT problem can potentially take exponential time.

        Likewise, many problems that are "undecidable" in general, such as the halting problem, can be solved in many common cases. It's just that given any program, any particular algorithm is potentially unable to determine whether it halts or not.

        Many people thi

    • Re: (Score:2)

      by vlm ( 69642 )

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

      And, critically, they're infeasible because the effort scales at higher than polynomial rates as the problem space increases.

      Perfectly feasible in 100 ms at 32 bits scales to 100 trillion years at 1024 bits. That kind of thing.

      Now its perfectly possible to find a poly solution, that scales polynomially, that is none the less completely infeasible and "has no application". Looking above, a poly solution might exist that cracks 32 bits in a mere 100 trillion trillion years, and scales linear so 1024 bits ta

    • Re: (Score:3)

      by amorsen ( 7485 )

      You can solve TSP for 1 million cities if you're willing to wait a few billion years

      No you can't. You can't solve TSP for 1 million cities before the expected heat death of the universe. You can't even solve TSP for 500 cities before the expected heat death of the universe (assuming you can do less than 10^100 instructions per second).

      • Re: (Score:2)

        by SashaM ( 520334 )

        You can solve TSP for 1 million cities if you're willing to wait a few billion years

        No you can't. You can't solve TSP for 1 million cities before the expected heat death of the universe.

        Umm, do you have a proof of that?

      • Re: (Score:2)

        by arth1 ( 260657 )

        Sure you can. You just can't verify the solution, because P != NP.
        But there's nothing that prevents you from guessing the correct solution in a millisecond.

    • Re: (Score:2)

      by Wildclaw ( 15718 )

      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.

      Are you sure there is enough energy in the whole universe to compute 2^1000000+ instructions? Even if time is not an issue, the laws of thermodynamics may very well be.

  • So, it has been proved that it is not possible to prove something we may or may not be able to prove?

    • So, it has been proved that it is not possible to prove something we may or may not be able to prove?

      No. It's been proven that this one proof is not a complete proof. There may be other proofs which will be proven to be proofs.

  • 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?

    • 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

  • Of course I also got the P NEQ NP one just in case...

Slashdot Top Deals

If all else fails, lower your standards.

Close