Forgot your password?
typodupeerror
Programming Science

Polynomial Time Code For 3-SAT Released, P==NP 700

Posted by CmdrTaco
from the heard-this-before dept.
An anonymous reader writes "Vladimir Romanov has released what he claims is a polynomial-time algorithm for solving 3-SAT. Because 3-SAT is NP-complete, this would imply that P==NP. While there's still good reason to be skeptical that this is, in fact, true, he's made source code available and appears decidedly more serious than most of the people attempting to prove that P==NP or P!=NP. Even though this is probably wrong, just based on the sheer number of prior failures, it seems more likely to lead to new discoveries than most. Note that there are already algorithms to solve 3-SAT, including one that runs in time (4/3)^n and succeeds with high probability. Incidentally, this wouldn't necessarily imply that encryption is worthless: it may still be too slow to be practical."
This discussion has been archived. No new comments can be posted.

Polynomial Time Code For 3-SAT Released, P==NP

Comments Filter:
  • by gman003 (1693318) on Thursday January 20, 2011 @11:42AM (#34940872)
    I tried to look the problem up on Wikipedia, and all I got was inscrutable high-level math. From what I can gather, I seems like something that could be explained in layman's terms. Would someone be kind enough to do so?
  • by sourcerror (1718066) on Thursday January 20, 2011 @11:54AM (#34941044)

    Please turn in your geek card. This is basic CS stuff.

  • by HarrySquatter (1698416) on Thursday January 20, 2011 @12:04PM (#34941228)

    Math is a big part of a CompSci degree now-a-day.

    lolwut? Since when has math NOT been a big part of computer science when computer science is a branch of mathematics? You must conflate computer science with programming or software engineering.

  • by Haedrian (1676506) on Thursday January 20, 2011 @12:12PM (#34941358)

    . . .

    "he's made source code available"

    Since checking the algorithm requires reading the source code - I would assume he's not spreading the source code of malware, because all interested parties WILL BE TRYING TO UNDERSTAND THE SOURCECODE.

  • by TheCycoONE (913189) on Thursday January 20, 2011 @12:19PM (#34941480)

    Well there probably should be at least one refuge where computer science nerds can discuss news that matters. Unlike mainstream media the news here shouldn't have to pander to the lowest common denominator - if you don't care for this article move on to one in a field that you are interested in. If you are not a nerd at all then news for nerds may not appeal to you.

  • by deapbluesea (1842210) on Thursday January 20, 2011 @12:30PM (#34941620)

    Absolutely untrue. All experts in the field that I've spoken to think that P is probably not equal to NP, but that a proof either way is going to be very hard.

    Absolutely correct. The difference between say, computer science and sociology, is that computer scientists require absolute proofs. In other words, if you claim that P==NP, as this paper does, then I require you to show that it is so for all possible inputs.

    The paper, in fact, does not show such a thing. To the contrary, it fails to show a sound and complete reduction of 3-SAT to hyperstructures, or CTF or CTS or whatever other acronyms were made up by the author. I'm not saying that he's wrong, simply that this is not a proof - it is only a claim. The author claims to have "proven" his algorithm is polynomial time by giving it a smattering of inputs and noting that the time the algorithm took to complete increased by a polynomial factor of the input size.

    Clearly the author has not studied his algorithmic complexity texts well enough to understand the definition of Big-O. Big-O only claims that algorithmic growth is asymptotic to a given curve as the input size goes to infinity from some value n0. In other words, many algorithms may display linear growth to a point, and then become exponential after input size greater than n0. A statistical analysis will not prove anything. The author needs to do a full algorithmic analysis instead.

    I predict this paper will be rapidly debunked and we will still not know if P==NP.

  • by marcosdumay (620877) <marcosdumay AT gmail DOT com> on Thursday January 20, 2011 @12:51PM (#34941900) Homepage Journal

    A small correction. The NP-Complete problem is "Is there any input for what it evaluates to true?". NP problems are exclusively yes/no ones.

    Now, if you solve the SAT problem, you can derive an algorithm for calculating the solution space. It will probably take exponential time. You can also derive an algorithm for finding an input that evaluates to true in polynomial time.

  • by EllisDees (268037) on Thursday January 20, 2011 @01:35PM (#34942482)

    Not to get completely off the subject, but there are many perfectly understandable proofs of why 0.999... = 1. For instance, one of the things that defines what a real number is that it is not exactly the same as a different number. Seems pretty common sense, huh? So what number, exactly, comes between 0.999... and 1? Like you said, those 9s go on forever, so if there is nothing that you can add to the first term to turn it into the second, they must be the same. They are just 2 different ways of expressing the exact same number. You probably don't have a problem with the idea that 1/3 = .333..., so multiply both sides by 3 and what do you get?

    There's even a wikipedia page that I'd totally paste in here if Chrome was able to do so.

     

  • by Anonymous Coward on Thursday January 20, 2011 @02:13PM (#34942988)

    You should read a little bit more about complexity theory and debunk your idea that because there are easy solutions to some problems for some sizes the solutions scale.

  • by Asmodae (1155077) on Thursday January 20, 2011 @02:24PM (#34943132)

    You probably don't have a problem with the idea that 1/3 = .333..., so multiply both sides by 3 and what do you get?

    You do get 1 = 1, but you don't get 1 = 0.999... like you claim you do. By analogy with limits, the limit of an equation as x approaches y is not the same as the same equation evaluated at x = y.

    Yes, yes it is. In fact that's the easiest way to calculate the limit if the function is defined at that point. It's just that functions that are defined at the limit you're looking for aren't particularly interesting. Limits get more interesting at asymptotes and infinity where you can't just plug in y into f(x).

We warn the reader in advance that the proof presented here depends on a clever but highly unmotivated trick. -- Howard Anton, "Elementary Linear Algebra"

Working...