CNF Generator for Factoring Problems

ignougroup
Problem Detail: I’ve been reading these:

I don’t understand how the reduction from FACT to $3text{-SAT}$ works. Are there any simple articles in which I can read about it? My final goal is to eventually implement a reduction from $3text{-SAT}$ to the undirected Hamiltonian circuit problem.

Asked By : Ilya_Gazman

Answered By : Realz Slaw

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 $3text{-SAT}$ (when you get to this step, you will understand this pretty easily)
  • There is a straightforward reduction from $text{Circuit-SAT}$ to $3text{-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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16789