4 ms·
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 pri
by mortehu 10y 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:
https://en.wikipedia.org/wiki/AKS_primality_test https://en.wikipedia.org/wiki/AKS_primality_test
- tgflynn 10y agoIt'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.
- mortehu 10y agoNeat. I wasn't aware of the trick of peeling off a bit at a time.