Skip to main content
Fix spelling error.
Source Link
D.W.
  • 165.6k
  • 21
  • 230
  • 490

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., tocheckto check whether $\varphi$ is satisfiable) is in $\textsf{AC}^0$, not that $\varphi$ is in $\textsf{AC}^0$.

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., tocheck whether $\varphi$ is satisfiable) is in $\textsf{AC}^0$, not that $\varphi$ is in $\textsf{AC}^0$.

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$.

Source Link
D.W.
  • 165.6k
  • 21
  • 230
  • 490

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., tocheck whether $\varphi$ is satisfiable) is in $\textsf{AC}^0$, not that $\varphi$ is in $\textsf{AC}^0$.