(Notes from parts of Chapter 15)
Let \(f,g:\mathbb{N} \rightarrow \mathbb{N}\). We say that \(f(n)\) is \(O(g(n))\) (read “big-O of g” or “of order \(g(n)\)”) if there exist constants \(a\) and \(b\) such that \(f(n) \leq a g(n) + b\) for all \( \mathbb{N} \). We write \(f(n) = O(g(n))\).
For example, \(x^2+3x + 4=O(x^2)\) because \(x^2 + 3x + 4 \leq 4x^2+4 \) for all \(x \geq 0\).
Note that it is also correct to write \(x^2 + 3x + 4=O(x^4)\) though this gives an asymptotic bound that is not as tight.
A language \(L\) on an alphabet \(A\) is said to be polynomial-time decidable if there is a deterministic Turing machine \({\cal M}\) that accepts \(L\) and a positive integer \(r\) such that the number of steps in an accepting computation by \({\cal M}\) with input \(x\) is \(O(|x|^r)\).
When the alphabet is fixed, we write \(\mathbf{P}\) for the class of polynomial-time decidable languages.
A total function \(f\) on \(A^*\), where \(A\) is an alphabet, is said to be polynomial-time computable if there is a Turing machine \({\cal M}\) that computes \(f\) and a positive integer \(r\) such that the number of steps in the computation by \({\cal M}\) with input \(x\) is \(O(|x|^r)\).
Theorem 2.1. Let \(L \in \mathbf{P}\). Let \(f\) be a polynomial-time computable function on \(A^*\). Let \[Q = \{ x \in A^* \mid f(x) \in L\}.\] Then \(Q \in \mathbf{P}\).
Theorem 2.2. Let \(f,g\) be polynomial-time computable functions. Let \(h(x) = f(g(x))\). Then \(h\) is polynomial-time computable.
A language \(L\) on an alphabet \(A\) is said to belong to the class \(\mathbf{NP}\) if there is a nondeterministic Turing machine \({\cal M}\) that accpets \(L\) and a positive integer \(r\) such that for each \(x\in L\), there exists an accepting computation \(\gamma_1,\ldots,\gamma_m\) by \({\cal M}\) with \(m = O(|x|^r)\).
Theorem 2.3. \(\mathbf{P} \subseteq \mathbf{NP}\). If \(L \in \mathbf{NP}\), then \(L\) is recursive.
It is not known if \(\mathbf{P} = \mathbf{NP}\). The problem of determining if \(\mathbf{P} = \mathbf{NP}\) is one of seven Millennium Problems. A solution to each of these problems is worth $1 million USD awarded by the Clay Mathematical Institute.
Let \(x_1,x_2,\ldots\) be variables that can be assigned the value TRUE or the value FALSE.
Propositional logic formulas are built up from the variables inductively using the following rules:
Each propositional variable is a formula.
If \(A\) and \(B\) are formulas, then so are \((\neg A)\), \((A \vee B)\), and \((A \wedge B)\).
The formula \((\neg A)\) is called the negation of \(A\).
The formula \((A \vee B)\) is called a disjunction of the disjuncts \(A\) and \(B\).
The formula \((A \wedge B)\) is called a conjunction of the conjuncts \(A\) and \(B\).
The symbols \(\neg\), \(\vee\), and \(\wedge\) are called logical connectives.
The following are propositional formulas:
\( ((x_1 \wedge x_2) \vee (\neg x_1)) \)
\( ((x_1 \wedge x_2) \vee ((\neg x_3) \wedge x_3)) \)
To avoid writing so many parentheses, we impose a precedence on the logical connectives: negation has precedence over conjunction and conjunction has precedence over disjunction. For example, the second example above can be written as \( x_1 \wedge x_2 \vee \neg x_3 \wedge x_3\). Though for ease of reading, we leave some of the parentheses in: \( (x_1 \wedge x_2)\vee (\neg x_3 \wedge x_3)\).
We also write \(A_1 \wedge A_2 \wedge \ldots \wedge A_k\) to mean \( (\ldots ( (A_1 \wedge A_2 ) \wedge A_3) \ldots ) \wedge A_k\), and \(A_1 \vee A_2 \vee \ldots \vee A_k\) to mean \( (\ldots ( (A_1 \vee A_2 ) \vee A_3) \ldots ) \vee A_k\),
Given a formula, a truth assignment is an assignment of the value TRUE or the value FALSE to each variable in the formula. For example, the following table shows all possible truth assignments for the formula \(x_1 \vee \neg x_2\).
| \(x_1 \) | \(x_2\) |
|---|---|
| TRUE | TRUE |
| TRUE | FALSE |
| FALSE | TRUE |
| FALSE | FALSE |
If a formula contains \(k\) variables, then there are a total of \(2^k\) possible truth assignments.
The valuation of a formula \(F\) at a particular truth assignment is defined recursively as follows:
If \(F\) is the single variable \(x_i\), then its valuation is simply the value assigned to \(x_i\).
If \(F\) is \((\neg x_i)\), then its valuation is TRUE if the value assigned to \(x_i\) is FALSE, and FALSE if the value assigned to \(x_i\) is TRUE.
If \(F\) is \((A \vee B)\), then its valuation is FALSE if the valuation of \(A\) and the valuation of \(B\) are both FALSE. Otherwise, the valuation is TRUE.
If \(F\) is \((A \wedge B)\), then its valuation is TRUE if the valuation of \(A\) and the valuation of \(B\) are both TRUE. Otherwise, the valuation is FALSE.
A formula \(F\) is said to be satisfiable if there exists a truth assignment at which the valuation of \(F\) is TRUE. A formula that is not satisfiable is said to be unsatisfiable.
The formulas in the example above are both satisfiable. The following formula is unsatisfiable: \[ x_1 \wedge \neg x_1.\]
A literal is either a variable or the negation of a variable.
A formula is said to be in conjunctive normal form (CNF) if it is of the form \[ C_1 \wedge C_2 \wedge \cdots \wedge C_k\] for some \(k \in \mathbb{N}\) where for each \(i = 1,\ldots, k\), \(C_i\) is a disjunction of literals and is called a clause. A clause is allowed to be empty. Any CNF formula with an empty clause is unsatisfiable.
Fact. Every propositional logic formula can be converted to an equivalent formula in CNF.
Note that the conversion might result in a formula whose length exponential in the length of the original formula. However, if we permit additional variables, we can obtain a formula that is satisfiable if and only if the original is but with length polynomial in the length of the original.
The following are CNF formulas:
\( (x_1 \vee \neg x_2 \vee x_3) \wedge (\neg x_1 \vee x_3 \vee \neg x_3 ) \)
\( x_1 \wedge (x_2 \vee \neg x_3)\)
We now describe a way to represent CNF formulas as strings over an alphabet.
The alphabet that we will use is \(A = \{ \alpha, \bar{\alpha}, |, /\}\).
The literal \(x_i\) is represented by \(\alpha |^{[i]}\); that is, \(\alpha\) followed by \(i\) copies of \(|\).
The literal \(\neg x_i\) is represented by \(\bar{\alpha} |^{[i]}\); that is, \(\bar{\alpha}\) followed by \(i\) copies of \(|\).
A clause is represented by \(/\) followed by the concatenation of the strings representing the literals in the clause. For example, the clause \( x_1 \vee \neg x_2 \vee x_3\) is represented by \( /\alpha | \bar{\alpha}|| \alpha |||\).
Finally, a CNF formula is represented by the concatenation of the strings representing the clauses. For example, the CNF formula \[ (x_1 \vee \neg x_2 \vee x_3) \wedge (\neg x_1 \vee x_3 \vee \neg x_3 ) \] is represented by \[ /\alpha | \bar{\alpha}|| \alpha ||| /\bar{\alpha} | \alpha||| \bar{\alpha}|||. \]
The language \(\text{SAT}\) is the language consisting of all elements of \(A^*\) that represent satisfiable CNF formulas.
Theorem 2.4. \(\text{SAT} \in \mathbf{NP}\)
We will describe informally a nondeterministic Turing machine that accepts \(\text{SAT}\).
We machine will have the following phases:
Checks if the input string represents a CNF formula.
Picks a truth assignment.
Checks if the valuation at the truth assignment is TRUE.
Let \(u \in A^*\) be the input string.
In Phase 1, the machine checks that \(x\) begins with \(/\) and that each \(/\) is not followed by \(|\) and that each \(\alpha\) or \(\bar{\alpha}\) is followed by \(|\). If \(u\) passes this check, then it is a string representing a CNF formula. The machine then moves the scanning head back to its starting position and transitions to Phase 2. Otherwise, it enters into an infinite loop. Note that Phase 1 can be completed in \(O(|u|)\) steps.
The intuition behind Phase 2 is as follows: The machine scans the string on the tape for a variable that has not been assigned a value. If every variable has been assigned a value, the machine moves the scanning head back to its starting position and transitions to Phase 3. Otherwise, the machine nondeterministically chooses a value to assign to this variable and go through the string to replace each literal of the variable to its valuation.
In order to properly estimate the number of steps Phase 2 requires, we need to know more details on how exactly the various actions can be carried out on a Turing machine. But let us first describe what we want to end up with on the tape when Phase 2 completes.
Let us first add two additional symbols: \(+\) and \(-\). Suppose that the machine decides to set the variable \(x_i\) to a value. As it scans the string on the tape, every time it encounters \(\alpha |^{[i]}\), it replaces it with \(+^{[i+1]}\) if the valuation is TRUE, and with \(-^{[i+1]}\) if the valuation is FALSE. Hence, once Phase 2 completes, the tape will consist of a string that has the same length as \(u\) and the only non-blank symbols are \(/\), \(+\), and \(-\).
In Phase 3, all the machine has to do is to check the string on the tape to see if after each \(/\) but before another \(/\) or a blank, there is a \(+\). If so, the valuation at the chosen truth assignment is TRUE and the machine halts. Otherwise, the machine enters an infinite loop. Note that the check can be performed in \(O(|u|)\) steps.
We now describe how the machine finds a variable that has not been assigned a value and how it looks through the string for matching literals and set them.
The machine first places the symbol \(\%\) right before the input string \(u\) before Phase 2 begins. In other words, the configuration at the beginning of Phase 2 is \[ \begin{array}{ccc} \% & u \\ \uparrow \\ q \end{array} \] where \(q\) is the initial state of Phase 2.
To find a variable that has not been assigned a value, the machine simply starts scanning from left to right until \(\alpha\) or \(\bar{\alpha}\) is found, bypassing any \(/\), \(+\), and \(-\). It then copies over the block of \(|\)'s that follows to the immediate left of \(\%\). This copying action will certainly need an extra symbol \(*\) for marking one at a time the \(|\)'s that have been copied. Also, after copying, the \(*\)'s have to be restored back to \(|\)'s. All the described actions can be done in \(O(|u|^2)\) steps. (Essentially, the machine creates a memory of which variable is being processed.)
The machine then nondeterministically chooses to enter Phase 2.T for setting the variable to TRUE or Phase 2.F for setting the variable to FALSE.
In either case, the machine starts scanning from left to right until \(\alpha\) or \(\bar{\alpha}\) is found, bypassing any \(/\), \(+\), \(-\), \(\phi\), and \(\bar{\phi}\), where \(\phi\) and \(\bar{\phi}\) are new symbols. (This takes \(O(|u|)\) steps.)
It then compares the string of \(|\)'s that follow with the string of \(|\)'s to the left of \(\%\). If they match in number, then replace the found \(\alpha\) or \(\bar{\alpha}\) and all the \(|\)'s that follow with \(+\)'s or \(-\)'s depending on the valuation. Otherwise, replace them with \(\phi\)'s if \(\alpha\) was found, or with \(\bar{\phi}\)'s if \(\bar{\alpha}\) was found instead. These actions will take \(O(|u|)^2\) steps since comparing two blocks requires an additional symbol for book-keeping and moving back and forth \(O(|u|)\) times.
Once no more matching literal can be found, the blocks of \(\phi\)'s and \(\bar{\phi}\)'s are restored to the literals they overwrote and the block of \(|\)'s to the left of \(\%\) gets blanked out. This takes \(O(|u|)\) steps. The machine then transitions back to the beginning of Phase 2.
As there are at most \(O(|u|)\) variables, the number of steps performed in Phase 2 is \(O(|u|^3)\).
In summary, the total number of steps performed in all three phases is \(O(|u|^3)\). Thus, \(\text{SAT} \in \mathbf{NP}\).