# Proof of Circuit-Sat to Nand-Sat polynomial time many–one reducibility

Given a gate called Nand with the following truth table:

A | B | A Nand B
------------------
0 | 0 |    1
0 | 1 |    1
1 | 0 |    1
1 | 1 |    0

We can define a circuit satisfiability problem where only Nand gates are allowed:

$\mathrm{Nand\text{-}Sat}$:

Input: A Boolean circuit $C$ with $m$ inputs $(P_{1},P_{2}\ldots,P_{m})$ such that all gates are Nand gates.

Question: Is there a Boolean assignment to the inputs of $C$ such that the output of $C$ is $1$?

I would like to show that $\mathrm{Circuit\text{-}Sat} \leq_{P} \mathrm{Nand\text{-}Sat}$. Where $\mathrm{Circuit\text{-}Sat}$ is the normal circuit satisfiability problem:

$\mathrm{Circuit\text{-}Sat}$:

Input: A Boolean circuit $C$ with $m$ inputs $(P_{1},P_{2}\ldots,P_{m})$.

Question: Is there a Boolean assignment to the inputs of $C$ such that the output of $C$ is $1$?

My question is do I have to create a function that translate AND,OR,NOT gates into Nand gates?

• You don't have to, but that would be a good way to go. – Rick Decker Mar 30 '15 at 1:31
• what's the other option ? thanks – mike10101 Mar 30 '15 at 2:15
• @mike10101 There isn't really another option, if you can construct the reduction, then you have to turn a normal Boolean circuit into a Nyet circuit, so all the gates, one way or another, end up encoded as Nyet gates. Working out how to turn the gates individually into Nyet gates is the easiest way. Try converting the NOT gate first - the conversion is "simple" (in the "not complicated" sense). – Luke Mathieson Mar 30 '15 at 6:06
• @LukeMathieson thanks ! here is what i did for the "Not" part (A and A) Or (A and notA) Or (notA and A) – mike10101 Mar 30 '15 at 7:12
• @mike10101 You want to go a slightly different route; try making a Not gate using only Nyet gates (a big hint is that you can do it with a single Nyet gate). – Luke Mathieson Mar 30 '15 at 7:15