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