Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The polynomial algorithm for 3-SAT problem (or P=NP)

romvf.wordpress.com

Post reply on HN
Print view View original

71–80 of 156 posts

Re: The polynomial algorithm for 3-SAT problem (or P=NP)

#71

Post by niyazpk »

spicyj wrote: post #56
jchonphoenix wrote: post #46

Earlier quoted context omitted.

You'd be surprised. Sometimes its much harder to find hidden faulty logic in a proof for an algorithm's correctness or running time. If I recall correctly, Ramanujan once wrote a proof for 1=2 that baffled mathematicians for quite some time before they figured out what was wrong. I believe that proof was rather short (< 1 page). For a long proof with a tiny error, things could be much worse.

Can you find a reference for Ramanujan's "proof"? I looked briefly and can't find one, but I'd be very interested to see what the proof was.

Here is one proof. I don't know if this can be attributed to Ramanujan.

    Let a, b be equal integers

    a = b
    a^2 = ab    // multiply by a
    a^2 + a^2 - 2ab = ab + a^2 - 2ab    // subtract a^2 - 2ab
    2(a^2 - ab) = a^2 - ab
    2 = 1
From p319, Fermat's Last Theorem by Simon Singh

Re: The polynomial algorithm for 3-SAT problem (or P=NP)

#72

Post by mitko »

xtacy wrote: post #47
tanis wrote: post #38

I've read the paper fairly closely, and it mostly seems like the author is hiding a conflict-driven search in ill-stated data structures, which allow him to perform a faulty analysis of the runtime of his algorithm. I've implemented a SAT solver and read the literature extensively. This paper is not up the standards of clarity imposed by that literature, see, eg, "Efficient Conflict Driven Learning in a Boolean Satis…

I would like to clarify that just because an algorithm runs slower than the ones used by solvers in competitions like SAT, it doesn't mean much, as we're looking at asymptotic complexity here. To give an example: the "PRIMES is in P" paper gives a poly time algorithm to determine if a given number is prime or not, but in practice, it runs slower than tests like probabilistic algorithms like Miller-Rabin.

Another example is Linear Programming - it is provably polynomial using the ellipsoid algorithm but people tend to use algorithms (such as simplex) which are not provably in P but run much faster in practice.

Re: The polynomial algorithm for 3-SAT problem (or P=NP)

#73

Post by sgk284 »

niyazpk wrote: post #71
spicyj wrote: post #56

Earlier quoted context omitted.

Can you find a reference for Ramanujan's "proof"? I looked briefly and can't find one, but I'd be very interested to see what the proof was.

Here is one proof. I don't know if this can be attributed to Ramanujan. Let a, b be equal integers a = b a^2 = ab // multiply by a a^2 + a^2 - 2ab = ab + a^2 - 2ab // subtract a^2 - 2ab 2(a^2 - ab) = a^2 - ab 2 = 1 From p319, Fermat's Last Theorem by Simon Singh

Just for those who don't see the error:

  2(a^2 - ab) = a^2 - ab
On this line, a^2 - ab is 0 (look at line 2). You wind up dividing both sides by 0, thus resulting in the false proof.

Re: The polynomial algorithm for 3-SAT problem (or P=NP)

#74

Post by mitko »

niyazpk wrote: post #71
spicyj wrote: post #56

Earlier quoted context omitted.

Can you find a reference for Ramanujan's "proof"? I looked briefly and can't find one, but I'd be very interested to see what the proof was.

Here is one proof. I don't know if this can be attributed to Ramanujan. Let a, b be equal integers a = b a^2 = ab // multiply by a a^2 + a^2 - 2ab = ab + a^2 - 2ab // subtract a^2 - 2ab 2(a^2 - ab) = a^2 - ab 2 = 1 From p319, Fermat's Last Theorem by Simon Singh

division by zero ?

Re: The polynomial algorithm for 3-SAT problem (or P=NP)

#75

Post by mitko »

dauphin wrote: post #40
slashcom wrote: post #28

Zero other (english) publications by the author in the Cornell archive and only four references within. Not an indicator as to whether the paper is correct (I haven't read it), but that's "smelly".

Yeah, and, seriously, a Russian?! Please...

Why not a Russian? For example the Russian Mathematics Olympiad is considered harder than the International Math Olympiad by many of the top contestants.

Edit: why downvoting?

Re: The polynomial algorithm for 3-SAT problem (or P=NP)

#76

Post by spicyj »

niyazpk wrote: post #71
spicyj wrote: post #56

Earlier quoted context omitted.

Can you find a reference for Ramanujan's "proof"? I looked briefly and can't find one, but I'd be very interested to see what the proof was.

Here is one proof. I don't know if this can be attributed to Ramanujan. Let a, b be equal integers a = b a^2 = ab // multiply by a a^2 + a^2 - 2ab = ab + a^2 - 2ab // subtract a^2 - 2ab 2(a^2 - ab) = a^2 - ab 2 = 1 From p319, Fermat's Last Theorem by Simon Singh

I'm guessing this isn't the proof that jchonphoenix referenced, because it has a fairly obvious error and most mathematicians would see it quite quickly.

Re: The polynomial algorithm for 3-SAT problem (or P=NP)

#77

Post by cperciva »

yhmv wrote: post #70
cperciva wrote: post #20

I'm not at all an expert on this material, but some random points to get people started: 0. This guy looks orders of magnitude less looney than the usual P=NP prover. I hope someone who knows this material well steps in soon. 1. This guy has implemented his algorithm. This is a very good sign -- most garbage "algorithms" are exposed to be broken when people try to implement them. 2. Most 3SAT problems are "easy". Bei…

Colin, no offense, and you are certainly a good coder & cryptographer, but that doesn't make know about everything in mathematics.

Err, what? I won the Putnam, but that's a mathematics competition, not a computational complexity competition.

Edit: If the above comment doesn't make sense, it's because the comment I was replying to was "you won the Neumann" and has since been edited.

Re: The polynomial algorithm for 3-SAT problem (or P=NP)

#78

Post by spicyj »

mitko wrote: post #75
dauphin wrote: post #40

Earlier quoted context omitted.

Yeah, and, seriously, a Russian?! Please...

Why not a Russian? For example the Russian Mathematics Olympiad is considered harder than the International Math Olympiad by many of the top contestants. Edit: why downvoting?

I interpreted dauphin's comment as sarcasm.

Re: The polynomial algorithm for 3-SAT problem (or P=NP)

#79

Post by wnoise »

cyrus_ wrote: post #24
jey wrote: post #2

Why do we think this is worthy of voting up? Is there any reason to think it might be correct?

It looks like the paper is fairly straightforward. It purports to give a polynomial time algorithm for 3-SAT. Interesting facts: - It is a O(n^4m) algorithm, where n is the number of boolean variables and m is the number of disjunctions. - It not only tells you whether the formula is satisfiable or not, but gives you the satisfying values. - The author claims to have implemented and tested the algorithm on reasonably…

> - It not only tells you whether the formula is satisfiable or not, but gives you the satisfying values.

Any yes/no NP solver can be turned into one that does this with polynomial overhead. After finding there is a solution, you ask it the similar problem "does this have solution with the first bit set to true?", then "does this have a solution with the first bit set to and the second bit set to true?", and so forth until you've identified all bits.

Post reply on HN