patternMinor
2-SAT or 3-SAT or k-SAT in AC-0
Viewed 0 times
satstackoverflowprogramming
Problem
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?
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#37614, answer score: 3
Revisions (0)
No revisions yet.