Skip to main content
Computer Science

Return to Question

Changed (3n choose 2) to (2n choose 3) for 3-SAT.
Source Link
Martin Seymour
Martin Seymour
  • 355
  • 1
  • 2
  • 7

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 ($3n$$2n$ choose 2$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?

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)$ 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 ($3n$ choose 2), 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?

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?

Source Link
Martin Seymour
Martin Seymour
  • 355
  • 1
  • 2
  • 7

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)$ 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 ($3n$ choose 2), 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?