Re: Factoring vs 3-SAT

From: David Wagner (daw_at_mozart.cs.berkeley.edu)
Date: 09/29/03 

Date: Mon, 29 Sep 2003 01:37:59 +0000 (UTC)

Paul Rubin wrote:
>daw@mozart.cs.berkeley.edu (David Wagner) writes:
>> One can multiple two k-bit numbers in O(k^2) time (and the hidden
>> constant is not large). Hence, the SAT formula will be of size n=O(k^2).
>
>What about the reduction from SAT to 3-SAT?

Actually, you can write the formula directly as a 3-SAT formula (no
need for the full power of SAT). If you ensure that every gate has 2
inputs and 1 output, then each gate in the multiplication circuit will
correspond to one 3-literal term in a 3-SAT formula. So, I don't think
there will be any blow-up in formula size from this consideration.

Quantcast