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.
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.
Probably caused by not understanding CPU architectures. Comparing two 8-bit integers and two 32-bit integers takes the same number of cycles on a 32-bit processor, but only because the CPU designers have accepted greater space complexity to reduce time complexity.
Comments
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
@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:
@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.
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.
Same disclaimer, but yes, assuming constant-time operations on arbitrary-precision integers represents a fairly common mistake in big-O analysis.
Probably caused by not understanding CPU architectures. Comparing two 8-bit integers and two 32-bit integers takes the same number of cycles on a 32-bit processor, but only because the CPU designers have accepted greater space complexity to reduce time complexity.
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.
One obvious mistake is on Page 2 (pseudo-code).
@Result = @Result | @ClauseResult
But @Result is 0 by default.