typodupeerror

## Polynomial Time Code For 3-SAT Released, P==NP700

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

• #### Re:What, exactly, is 3-SAT? (Score:5, Funny)

on Thursday January 20, 2011 @01:08PM (#34941290)
Linguam romanae scio. Latina difficila non est; ego in annis tribus didici.
• #### Goldbach Conjecture (Score:5, Funny)

on Thursday January 20, 2011 @01:12PM (#34941350) Journal

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 (Score:4, Funny)

on Thursday January 20, 2011 @01:19PM (#34941460)
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 (Score:5, Funny)

on Thursday January 20, 2011 @01:22PM (#34941520) Journal

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 (Score:5, Funny)

on Thursday January 20, 2011 @01:24PM (#34941536) Homepage Journal

what does P stand for?

Portman.

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

• #### Interesting... (Score:4, Funny)

on Thursday January 20, 2011 @01:27PM (#34941574)
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:I'll be first to say WTF (Score:4, Funny)

on Thursday January 20, 2011 @02:01PM (#34942060)
Maybe there wasn't enough space in the margin.
• #### Re:I'll be first to say WTF (Score:5, Funny)

on Thursday January 20, 2011 @02:05PM (#34942110)
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? (Score:4, Funny)

on Thursday January 20, 2011 @02:15PM (#34942224)
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? (Score:4, Funny)

on Thursday January 20, 2011 @02:30PM (#34942394)
Romanes eunt domus.
• #### Re:I'll be first to say WTF (Score:5, Funny)

on Thursday January 20, 2011 @02:40PM (#34942536) Journal

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? (Score:5, Funny)

on Thursday January 20, 2011 @02:45PM (#34942630)

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

smartass...

• #### Re:Interesting... (Score:5, Funny)

<corbettw&yahoo,com> on Thursday January 20, 2011 @02:47PM (#34942652) Journal

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 (Score:3, Funny)

on Thursday January 20, 2011 @03:22PM (#34943108)
And if one of those cities is Konigsberg he'll never get it done...

#### Related LinksTop of the: day, week, month.

I THINK MAN INVENTED THE CAR by instinct. -- Jack Handley, The New Mexican, 1988.

Working...