Comment by mortehu
10 years ago
The satisfiability problem doesn't require that you provide the solution, only that you determine whether or not a solution exists. So you'd end up with a primality check, which is known to be in P:
10 years ago
The satisfiability problem doesn't require that you provide the solution, only that you determine whether or not a solution exists. So you'd end up with a primality check, which is known to be in P:
It's not a primality test. A primality test determines whether or not a single given integer is prime.
The circuit I described checks that the product of two arbitrary input integers is a specific known integer.
By solving the decision problem for each bit independently you can determine all bits of the 2 input integers and hence factor the known target.
Neat. I wasn't aware of the trick of peeling off a bit at a time.