# 2-SAT or 3-SAT or k-SAT in AC-0

This may be an elementary question, but I'm new to circuit complexity. Does 2-SAT in CNF form belong to the complexity class AC$^0$?

It seems simple enough to construct an AC$^0$ circuit of depth 2 of polynomial size for 2-SAT. $~$Given $n$ variables (which means $2n$ literals), there can be at most $\frac{(2n)(2n-1)}{2} = n(2n-1)$ number of OR gates at Level one, because, given $2n$ literals, there can be at most $n(2n-1)$ clauses. At Level 2, there is just one gate (an AND gate).

But we can also extend this to 3-SAT. $~$The only difference is that at Level one, the maximum number of OR gates would now be ($2n$ choose $3$), which is $O(n^3)$, still polynomial in the number of variables. Doesn't this mean that 3-SAT is also a member of AC$^0$? Wouldn't this mean that 3-SAT is polynomially solvable? What am I doing wrong?

• You're showing that each instance is in AC0, not that those problems are in AC0. $\;$
– user12859
Jan 26, 2015 at 9:48

2SAT is the following problem: given $\varphi$ (a Boolean formula in 2-CNF), is $\varphi$ satisfiable?
To show that 2SAT is in $\textsf{AC}^0$, you must show a constant-depth, polynomial-size circuit that can solve 2SAT. In other words, you need to come up with an algorithm to solve 2SAT, and then show that the algorithm can be implemented by an $\textsf{AC}^0$ circuit.
In your question, you showed that $\varphi$ is in $\textsf{AC}^0$, but that's not what we need. We need to know that the algorithm to solve 2SAT (i.e., to check whether $\varphi$ is satisfiable) is in $\textsf{AC}^0$, not that $\varphi$ is in $\textsf{AC}^0$.
• Thanks.. We know that 2-SAT is complete for NL under AC$^0$ reductions.. So the reduction algo that converts an instance of an NL problem to an instance of 2-SAT can be represented by an AC$^0$ circuit, right? Okay... Jan 26, 2015 at 19:49