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

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

Comments

Re:What, exactly, is 3-SAT?

[gman003]

Linguam romanae scio. Latina difficila non est; ego in annis tribus didici.

Goldbach Conjecture

[Bazman]

I have code for a solution to the Goldbach Conjecture, but it doesn't fit into my free storage on github....

Re:I'll be first to say WTF

[UnknowingFool]

Like you, I have no idea what the article or summary means. Unlike you, in the finest traditions of slashdot, I will have strong opinions here shortly like I have in many other subjects. Abrasive, irrefutable, and loud ones.

Re:I'll be first to say WTF

[TheRaven64]

Are we expected to get a CS degree before reading Slashdot?

Yes. And a PhD before posting. Didn't you read the T&Cs?

Re:I'll be first to say WTF

[Qubit]

what does P stand for?

Portman.

Oh wait, sorry, I was answering the comment above yours...

Interesting...

[shadowrat]

I can't really comment on the validity of the claims in the article. It's unclear if he has indeed proven P==NP. I do know that this article clearly proves I am only of average or slightly sub average intelligence.

Re:Interesting...

[corbettw]

Welcome to the club. My friends and colleagues routinely think of me as "one of the smartest people they know" (or so I've been told). Articles like this remind me of my true status, which is helpful in not getting cocky.

Re:I'll be first to say WTF

[SandFrog]

Maybe there wasn't enough space in the margin.

Re:I'll be first to say WTF

[daremonai]

Here you go: Let's say you want to have sex with Natalie Portman (NP). Up until now, it was generally assumed that meant you had to satisfy three conditions: be rich, handsome, and fascinating. Unfortunately, any one of those would leave out the vast majority of people on this list; satisfying all three (3-SAT) was considered virtually impossible.

But now, Romanov claims that it is sufficient merely to say the mathematical equivalent of "Please" (P). Naturally, people are skeptical.

Re:What, exactly, is 3-SAT?

[robthebloke]

No, i believe the correct translation is:

"Roman sharks, with frickin' laser beams attached to their latin heads".

But then again, I don't read latin much anymore, so I may have made the odd grammatical error...

Re:What, exactly, is 3-SAT?

[Tenek]

Romanes eunt domus.

Re:I'll be first to say WTF

[snowgirl]

And if each car is located in a different city, then he'll have to go travelling in order to test all the criteria. Of course, he wouldn't want to end up hitting the same city twice...

Re:What, exactly, is 3-SAT?

[prionic6]

If you're so good at it, at least translate the line for us!

smartass...

Re:I'll be first to say WTF

[logical1010]

And if one of those cities is Konigsberg he'll never get it done...