3
$\begingroup$

In the paper https://web.stanford.edu/~gavish/documents/sipser-pvsnp.pdf , it is mentioned under the Status section that boolean circuits have been used to try and solve P vs NP. Can anyone explain to me in simple terms how boolean circuits are used for solving P vs NP?

$\endgroup$
5
$\begingroup$

First, let me start by explaining what Boolean circuits are. You are probably familiar with Boolean formulas — these are formulas of the sort $(a \land b) \lor (\lnot a \land \lnot b)$. We can represent each formula as a tree. In our example, the root of the tree will be labeled $\lor$, and its two children are the trees corresponding to $a \land b$ and $\lnot a \land \lnot b$. More generally, there are four types of nodes: nodes labeled $\lor$ or $\land$ have exactly two children, nodes labeled $\lnot$ have exactly one child, and the rest of the nodes are labeled by input variables. We can think of the edges as directed towards the root.

Boolean circuits generalize Boolean formulas by allowing arbitrary directed acyclic graphs instead of directed trees. In the example above, we can, for example, identify the two nodes labeled $a$ and the two nodes labeled $b$. Alternatively, we can identify Boolean circuits with straightline programs. These are programs which use the following instructions:

  • $x \gets y \lor z$.
  • $x \gets y \land z$.
  • $x \gets \lnot y$.

For example, the formula above corresponds to the straightline program

  • $x \gets a \land b$.
  • $y \gets \lnot a$.
  • $z \gets \lnot b$.
  • $w \gets y \land z$.
  • $o \gets x \lor w$.

The value of the formula is the value of the last assignment. Notice that every variable other than the inputs is used exactly once. Straightline programs with this constraint correspond to formulas. If we remove the constraint, the we get circuits.


The $\mathsf{P} \neq \mathsf{NP}$ conjecture can be stated equivalently as follows:

SAT has no polynomial time algorithm.

It turns out that the following conjecture (known as $\mathsf{P/poly} \neq \mathsf{NP}$) implies $\mathsf{P} \neq \mathsf{NP}$:

SAT has no polynomial size circuits.

What does this mean? We can encode CNFs as strings of bits (for example, encode them first in ASCII, and then unfold the ASCII into bits). Let $SAT_n$ be the collection of satisfiable CNFs of length $n$ bits. A circuit for $SAT_n$ is a circuit on $n$ inputs $x_1,\ldots,x_n$ which returns True if and only if $x_1\ldots x_n \in SAT_n$, i.e., the CNF corresponding to $x_1\ldots x_n$ is satisfiable. We say that a collection of circuits $C_1,C_2,\ldots$ solves SAT if $C_n$ is a circuit for $SAT_n$. The collection has polynomial size if there exists a polynomial $P(n)$ such that the size of $C_n$ is at most $P(n)$ (the size of a circuit is the number of nodes in its graphical representation).

Why does this imply that SAT has no polynomial time algorithms? The reason is (essentially) the Cook–Levin theorem. This theorem shows that if SAT has a polynomial time algorithm then it also has polynomial size circuits. There is nothing special about SAT here — this reduction works for every problem. The theorem shows how to encode the computation of a Turing machine running in polynomial time as a polynomial size circuit.


Unfortunately, we are very far from realizing this program. We only know how to show that polynomial size circuits cannot solve certain problems in the following circumstances:

  • When the circuit is shallow, that is, has small depth.
  • When the circuit doesn’t use $\lnot$ gates at all.
  • For non-explicit problems: by counting the number of polynomial size circuits (for any fixed polynomial), you can show that there must be some functions that they cannot compute.

There is some further progress which throws diagonalization into the mix, but that’s about it. It seems that this approach is stuck, and different lines of attack are required to solve this important problem.

$\endgroup$
1
$\begingroup$

Despite being called "circuits", Boolean circuits are essentially the same thing as Boolean formulas. This means that questions about Boolean circuits are exactly questions about SAT, which is the prototypical NP-complete problem.

$\endgroup$
  • $\begingroup$ Alright. Thank you. I have problem understanding how monotone circuits and Bounded Depth circuits are used for P vs NP. Can you explain it to me? $\endgroup$ – Saad May 10 '18 at 15:39
  • $\begingroup$ @Saad They just correspond to restrictions on the formula. Monotone means no negations; bounded depth is about the maximum amount of nesting of ANDs and ORs. So these people are studying restricted classes of formulas/circuits and looking at how, e.g., the computational resource requirements depend on the depth of the circuit as a way to get a handle on how all circuits behave. $\endgroup$ – David Richerby May 10 '18 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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