Claim: Algorithm that Solves 3-SAT in Polynomial Time (arxiv.org)

P=NP was solved 6 days ago and no one told me? Anyone want to point out the error here?

A 5 page paper by a previously unpublished author with no associated institution? How does this have any credibility?

Same old, same old.. Waiting for the debunk post.

I haven't analyzed this algorithm for correctness (nor even understood it), but it doesn't run in polynomial time. In every iteration of the outer loop, it compares 2^2^n bits, where n is the number of variables. It looks like he's basically encoding the problem as a bit string and then comparing it.

Oh, please, the arXiv is full of proofs that either P=NP or P != NP (sometimes the same author proves one thing, then changes his mind and proves the opposite).

For this one in particular it is very easy to find the flaw

    Let @Unsolvable = (2 ^ (2 ^ Variables.Count)) - 1

@Unsolvable has 2^Variables bits, so it can't be computed in polynomial time. This is a typical fallacy by novices: assume that all arithmetic operations can be computed in constant time and constant space, regardless of the precision.

The encoding looks fine, but the algorithm isn't polynomial. Examine the following:

  Let @Unsolvable = (2 ^ (2 ^ Variables.Count)) - 1

  ...

  If @Result = @Unsolvable
    Return FALSE /*the formula cannot be satisfied*/
  End if

@Unsolvable is exponential in the number of variables in the CNF. Thus there's an assumption here that the machine has a data-type capable of containing arbitrarily large integers.

For example, if there are 10 variables, then @Unsolvable is 2^2^10-1. And so on. It doesn't matter whether his loops are polynomial, within the loops he's got something exponential in the number of variables.

One obvious mistake is on Page 2 (pseudo-code).

@Result = @Result | @ClauseResult

But @Result is 0 by default.