3
$\begingroup$

I've been reading these:

I don't understand how the reduction from FACT to $3\text{-SAT}$ works. Are there any simple articles in which I can read about it?

My final goal is to eventually implement a reduction from $3\text{-SAT}$ to the undirected Hamiltonian circuit problem.

Improve this question
$\endgroup$
7
  • $\begingroup$ What do you mean by "CNF"? Do you mean SAT? CNF is a form of boolean formulas, not a term describing a problem (that I am aware of). We know SAT is NP-complete, and we know that finding the factorization of any integer is in NP (the certificate is the factorization, the verifier just checks whether the factors multiply to the integer and that each of them is prime). $\endgroup$
    – G. Bach
    Commented Nov 7, 2013 at 13:06
  • $\begingroup$ @G.Bach CNF is just a way to output sat. $\endgroup$
    – Ilya Gazman
    Commented Nov 7, 2013 at 13:10
  • $\begingroup$ SAT is the solution of CNFs aka associated "decision problem". $\endgroup$
    – vzn
    Commented Nov 7, 2013 at 23:41
  • $\begingroup$ @vzn Associating SAT with CNF only feels natural because that is the way it is most relevant in CS. Introduced differently, we could just as well associate the question of whether a formula in CNF is a tautology/contradiction with CNF, had it been used most prominently in that way. Since Cook used SAT, that is the way we think about CNF formulas. Had he used, say, the Hamiltonian cycle problem, then we might well associate CNF with something else. $\endgroup$
    – G. Bach
    Commented Nov 8, 2013 at 1:14
  • 1
    $\begingroup$ How does understanding the reduction from FACT to 3SAT help with your goal of producing a reduction from 3SAT to HAMCYCLE? Standard reductions from 3SAT to VERTEX COVER to HAMCYCLE have been known since the 1970s and are covered in any textbook on complexity theoy (e.g., sections 3.1.3 and 3.1.4 of Garey and Johnson). They have nothing to do with integer factorization. $\endgroup$
    – David Richerby
    Commented Nov 22, 2013 at 13:40

2 Answers 2

Reset to default
6
$\begingroup$

I don't understand how the reduction from FACT to 3-SAT works. Are there any simple articles in which I can read about it?

Most of the reading material assumes several steps of knowledge.

  • First, you should read about how logic circuits (logic gates) work.
  • Optionally learn or use a simple multiplication algorithm. You might want to start with the long-multiplication algorithm that everyone learns in school.
  • Then research and understand a multiplication circuit, and/or learn how to convert the chosen algorithm to a circuit.
  • You should now know how to make a simple multiplication circuit (MULT). Next learn to extend it for $n$-bit numbers.
  • Once you have a circuit, you can force the outputs of the circuit to the $N$ value you want to factor. You do this by taking the $n$ outputs, and point-wise xoring them together with your $N$ value. Set the final output to be true iff $N$ and the MULT output cancel each-other out. You can do this by first oring all the xor results; if they are all $0$, then the output matched $N$ (in this case, set the final output to be $1$, else $0$).
  • Now you have $\text{Circuit-SAT}$. Learn about $\text{Circuit-SAT}$.
  • $\text{Circuit-SAT}$ asks if there is an input that can satisfy the output. $\text{Circuit-SAT}$ is an NP-complete problem, that is almost directly convertible to $3\text{-SAT}$ (when you get to this step, you will understand this pretty easily)
  • There is a straightforward reduction from $\text{Circuit-SAT}$ to $3\text{-SAT}$ available here: Convert Circuit SAT to 3-SAT

You can't get it all in one scoop without talking to someone in-person. Rather you should follow the steps, without skipping. Each of these has "simple" material to learn from; but you'll not find one that teaches you everything in one sitting from the very basics.

Also see Computer Organization - Module II, section 2.5.1 Array Multiplier, which implements a carry-save-array-multiplication circuit:

Looks a lot like grade-school multiplication, doesn't it ...

Each box is (FA means "Full adder", which is also on that page in section 2.2 Serial & Parallel Adder): enter image description here

Improve this answer
$\endgroup$
3
$\begingroup$

there are several ways to conceptualize this, esp using the psychological concept of chunking which is rougly equivalent to the use of "abstraction(s)" in CS. what part is hard to understand? the conversion of factoring to SAT is much easier to understand if you learn how EE circuits implement binary arithmetic (mainly addition), and to note that multiplication is repeated addition of a shifted multiplicand, and in binary multiplication, this is reduces to bits of the multiplier simply "masking" the shifted multiplicand.

the SAT formula specifies, via a set of constraints, a relation between "input" and "output" bits equivalent to binary multiplication. it is actually like a 2-way computation device because it naturally computes in a forward direction $f(x,y)= x \cdot y = z$ and in a "reverse" (inverse) direction $f^{-1}(z)=x \cdot y$.

for multiplication implemented in SAT, specify the "input" bits, and leave "output" bits unassigned (via what are called "unit clauses") and solve the CNF formula for "output" bits. for factoring, specify the "output" bits without specifying the "input" bits.

in EE addition circuits are called "half/full adders". then the only task is to convert these circuits into SAT (CNF) formulas. binary addition of bit vectors is done most simply with a string of full adders where each carry bit feeds into the next stage of the addition, the so-called "ripple carry adder".

here is a nice slideshow on converting binary/bitvector arithmetic to propositional logic aka "bitblasting". on slide 8 the CNF formula for a full adder is given. slide 10 has the same ripple carry adder.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.