Boolean Decision Problem

Q. CNF Satisfiability Problem. (=CNF-SAT =Circuit Satisfiability) Given a conjunctive normal form, is there a way to set the variables to $\text{True}$ or $\text{False}$ such that the formula evaluates to $\text{True}$?

$$(x_1\vee \neg x_2\vee x_3)\wedge (\neg x_1\vee x_4)\wedge (x_2\vee \neg x_3\vee x_5\vee \neg x_6)$$

• Literal: $x_i$ or $\overline{x_i}$
• Clause: $(x_1\vee x_2\vee \overline{x_3})$ a set of or-connected literals

thm. Cooke-Levin Theorem. The Boolean Satisfiability problem is NP-complete.

• The first problem to be determined to be NP-complete.

Q. 3-Satisfiability Problem. (3-SAT)

• The CNF-SAT problem, but every set of ORs has only three variables
• 3-SAT ${\le }_p$ 4-SAT

alg. Reduction CNF-SAT ${\le }_p$ 3-SAT

• Idea: $a\vee b\equiv (a\vee c)\cap (b\vee \bar{c})$……(1)

1. Construction
   1. $\exists \{x_1\dots x_n\}$ variables that satisfies $Q:q_1\dots q_m$ where $q_i$ is a clause
   2. $Q^{\prime }:q_1^{\prime }\dots q_{m^{\prime }}^{\prime }$ constructed to satisfy (1).
      1. $m^{\prime }>m$ (obviously)
      2. New variables $v_1\dots v_k$ thus $Q$ has variables $\{x_1\dots x_n,v_1\dots ,v_k\}$
2. CNF-SAT ⇒ 3-SAT
   1. let $X_1\dots X_n\in \{0,1\}$ that satisfies $Q$. Then these values will satisfy $Q^{\prime }$ regardless of $v_i$ ’s values, so choose them arbitrarily. These values satisfy $Q^{\prime }$
3. 3-SAT ⇒ CNF-SAT
   1. let $X_1\dots X_n,V_1\dots V_n\in \{0,1\}$ that satisfies $Q^{\prime }$. Then $X_1\dots X_n$ will satisfy $Q$.
4. Thus proven.

Q. DNF Satisfiability Problem. Given a disjunctive normal form, is there a way to set the variables to $\text{True}$ or $\text{False}$ such that the formula evaluates to $\text{True}$?

• Exists a Polynomial time algorithm
• Only one clause need be satisfied

Q. Tautology. Given a Boolean formula $Q$, is $Q$ always $\text{True}$ regardless of what the variables are set to?

• The verification procedure for $\text{True}$ itself is NP-Complete, and it is exactly the CNF Satisfiability problem
• The verification procedure for $\text{False}$ is also NP-hard
• The whole problem is not in NP (and is Co-NP Complete)