Polynomial Time Code For 3-SAT Released, P==NP 700
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."
What, exactly, is 3-SAT? (Score:4, Insightful)
Re:I'll be first to say WTF (Score:4, Insightful)
Please turn in your geek card. This is basic CS stuff.
Re:I'll be first to say WTF (Score:3, Insightful)
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.
Re:Nice way to spread malware? (Score:5, Insightful)
. . .
"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.
Re:I'll be first to say WTF (Score:5, Insightful)
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.
Re:I'll be first to say WTF (Score:5, Insightful)
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.
Re:What, exactly, is 3-SAT? (Score:4, Insightful)
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.
Re:I'll be first to say WTF (Score:5, Insightful)
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.
Re:My personal wild guess (Score:2, Insightful)
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.
Re:I'll be first to say WTF (Score:3, Insightful)
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).