A decision problem is a problem for which the answer is YES or NO. It can be defined as a finite set of parameters.
If we fix the values of the parameters we get an instance of the problem.
Encoding of a decision problem \Pi is a function e: D_\Pi \to \Sigma^* where \Sigma is an alphabet. For a decision problem \Pi and an encoding e fo \Pi there is a corresponding language
L(\Pi,e) = L_\Pi = \{e(I) \in \Sigma^* : I \in Y_\Pi\}
\Pi is called decidable if L_\Pi \in R otherwise \Pi is called undecidable.
Example: encoding of natural number n on the tape of a TM:
subjective
Instance: two lists A = w_1, w_2, \cdots, w_k and B = x_1, x_2, \cdots, x_k of strings over \Sigma. A solution is a finite sequence of indices i_1, i_2, \cdots, i_m m \ge 1 such that w_{i_1} \circ w_{i_2} \circ \cdots \circ w_{i_m} = x_{i_1} \circ x_{i_2} \circ \cdots \circ x_{i_m}
It is the standard PCP but with the condition that i_1 = 1
lemma: if PCP is decidable then MPCP is decidable.
If there exists an algorithm for solving PCP then there exists an algorithm for solving MPCP.
theorem: PCP is undecidable. By lemma it suffices to show that if MPCP is decidable then L_u \in R.
A problem of finding a minimum/maximum of a objective function.
G - graph,
| optimization problem | decision problem |
|---|---|
| \chi(G) =\ ? | does exist a proper vertex coloring of G with k colors? |
For I \in D_\Pi |I| = size of I.
For every reasonable encoding e there exist polynomials p, p' such that |I| \le p(|e(I)|) and |e(I)| \le p'(|I|) for every I \in D_\Pi.
Example of standard encoding scheme:
\Sigma = \{0, 1, -, [, ], (, ), ,\}
We recursively define structured strings
A - algorithm, I \in D_\Pi, |I| = input size = the number of cells of A used to input I (|e(I)|)
The time complexity of A is a function T_A: N \to N
T_A(n) = \max_{I \in D_\Pi, |I| = n}\{\text{the number of steps performed by A during the computation on input I}\}
NTM with stop property. The tree of computation is finite. Halts for every sequence of choices.
Let A be a non-deterministic algorithm for solving \Pi.
The time complexity of A is a function T_A: N \to N
T_A(n) = \max_{I \in D_\Pi, |I| = n}\{\sup(\text{number of moves in every path from root to a leaf in the computation tree of A on input I})\}
f, g: N \to \mathbb R (increasing functions)
f(n) = O(g(n)) if \exists_{C > 0} \exists_{n_0 \in N} \forall_{n \ge n_0} f(n) \le C \cdot g(n)
A is called a polynomial time algorithm if there exists a polynomial p such that T_A(n) = O(p(n)). Otherwise A is called an exponential time algorithm.
L_1 \subseteq \Sigma_1^*, L_2 \subseteq \Sigma_2^* - languages
A polynomial time transformation from L_1 to L_2 is a function f: \Sigma_1^* \to \Sigma_2^* such that
denoted by L_1 \alpha L_2
\Pi_1, \Pi_2 - decision problems
A polynomial time transformation from \Pi_1 to \Pi_2 is a function f: D_{\Pi_1} \to D_{\Pi_2} such that
denoted by \Pi_1 \alpha \Pi_2
This relation is reflexive and transitive.
Theorem: L \in NP \iff there exists a language L_{\text{check}} \in P and a polynomial p such that L = \{x : \exists_{y} (x, y) \in L_{\text{check}} \land |y| \le p(|x|)\}. y is called a certificate for x.
Proof:
\impliedby
Let M be a deterministic algorithm such that L(M) = L_{\text{check}}. We construct a non-deterministic algorithm M' such that L(M') = L. First M' guesses y (the number of candidates is bounded because |y| \le p(|x|)). Then M' runs M on (x, y) and checks the answer.
\implies
Let M be a nondeterministic algorithm such that L(M) = L. Computation of M on input string x. Any path from the root in the tree of computation of M on input x has length \le p(|x|) for some polynomial p. We define L_{\text{check}}. (x, y) \in L_{\text{check}} \iff y is a code of computation path of M on input x which ends in accepting state. Now we show that L_{\text{check}} \in P. We construct a deterministic algorithm M' such that L(M') = L_{\text{check}}. M' check if y is a correct code of computation path of M on input x and checks if it ends in accepting state.
If \Pi_1, \Pi_2 \in NP, \Pi_1 \in NPC and \Pi_1 \alpha \Pi_2 then \Pi_2 \in NPC.
If \Pi \in NP then \Pi can be solved on DTM in exponential time. Question: if \Pi \in NP then can \Pi be solved on DTM in polynomial time?
Logic formula in CNF = a conjunction of clauses, each clause is a disjunction of literals, a literal is a variable or negated variable.
Example: F = (x_1 \lor \neg x_2 \lor x_3) \land (\neg x_1 \lor x_2) \land (\neg x_2 \lor x_3 \lor \neg x_4)
X = \{x_1, \cdots, x_n\} a set of variables, F - a formula in CNF with variables from X. An assignment is v: X \to \{0, 1\}. There are 2^n assignments.
Question: does there exist an assignment v that satisfies F? Such assignment is called a satisfying assignment. v satisfies F \iff v satisfies every clause of F.
\text{SAT} \in NPC.
We construct a NTM with stop property M for solving \text{SAT}. First M guesses an assignment (O(n)) and then checks if this assignment satisfies every clause (polynomial time).
Let M be a NTM with stop property such that L(M) = L. Let w be an input string. We will construct f(w) - an instance of \text{SAT} such that w \in L \implies f(w) is satisfiable. We assume M has one tape. Let p(n) be a polynomial such that T_M(n) \le p(n). We can assume that p(n) \ge n. M = (Q, \Sigma, \Gamma, \delta, B, q_1, \{q_s\}, \{q_{s-q}\}) with Q = \{q_1, \cdots, q_s\}, \Gamma = \{X_1, \cdots, X_m\}, B = X_m, s, m - const. Let |w| = n. We assume that if M finishes the computation before p(n) steps then it stays in the accepting state or the rejecting state and halts in moment p(n), so the computation of M always takes p(n) steps. Variables:
There are p(n) \cdot m \cdot (p(n) + 1) + s \cdot (p(n) + 1) + p(n) \cdot (p(n) + 1) = \Theta(p^2(n)) variables. By |F| we denote the length of the formula = the number of literals in F. Let U(x_1, \cdots, x_r) = (x_1 \lor x_2 \lor \cdots \lor x_r) \land (\neg x_1 \lor \neg x_2) \land (\neg x_1 \lor \neg x_3) \land \cdots \land (\neg x_{r-1} \lor \neg x_r). So U(x_1, \cdots, x_r) = 1 \iff for exactly one i \in \{1, \cdots, r\}, x_i = 1. |U| = O(r^2). There will be 7 types of clauses in f(w) describing conditions.
So f(w) = F_1 \land F_2 \land F_3 \land F_4 \land F_5 \land F_6 \land F_7. The number of literals in f(w) is O(p^3(n)). There are \Theta(p^2(n)) variables \implies the length of variable is O(\beta\log n) where \beta depends on p. The length of |f(w)| = O(p^3(n) \beta \log n) = O(p^4(n)). f(w) = 1 \iff M halts in accepting state \iff w \in L(M) = L. f(w) can be constructed in polynomial time. \square
A dominating set in a graph G is a set W \subseteq V such that \forall_{v \in V \setminus W} v has at least one neighbor in W.
Instance: G=(V, E), k \in N
Question: Does there exist a dominating set W in G such that |W| \le k?
K_n - complete graph, w: E(K_n) \to N - a weight function, b \in N
Instance: K_n, w, b
Question: Does there exist a Hamiltonian cycle v_1v_2\cdots v_nv_1 in K_n such that \sum_{i=1}^{n-1}w(v_iv_{i+1}) + w(v_nv_1) \le b.
X = \{x_1, \cdots, x_n\} f: X \to N - a weight function.
Instance: X, f
Question: Does there exist a set X' \subseteq X such that \sum_{x_i \in X'}f(x_i) = \sum_{x_i \in X \setminus X'}f(x_i)
For W \subseteq V the following conditions are equivalent:
So these 3 problems can be seen as different versions of the same problem. Any of these problems can be easily transformed to either of the others. For instance, to transform VC to Clique: let (G = (V, E), k) be an instance of VC. The corresponding instance of Clique is (\bar G, |V| - k) which can be obtained with a transformation in polynomial time. Thus if one of the problems is NPC, then other are too.
A nondeterministic algorithm guesses a subset of vertices and checks in polynomial time whether this subset is a VC and has correct cardinality.
Let X = \{x_1, \cdots, x_n\} and let F = c_1 \land \cdots \land c_m be a \text{3SAT} instance. We will construct a graph G = (V, E) and a natural number k \le |V| such that G has a vertex cover of cardinality at most k \iff F is satisfiable.
Components: truth-setting components + satisfaction testing components + communication edges.
For every variable x_i there is a truth-setting component T_i = (V_i, E_i) where V_i = \{x_i, \neg x_i\} and E_i = \{\{x_i, \neg x_i\}\}, so it is a K_2. Note that any vertex cover will have to contain at least one of the two vertices of E_i in order to cover this edge.
For every clause c_j in F there is a satisfaction testing component S_j = (V_j', E_j') where V_j' = \{a_1(j), a_2(j), a_3(j)\} and E_j' = \{\{a_1(j), a_2(j)\},\{a_1(j), a_3(j)\},\{a_2(j), a_3(j)\}\} so it is a K_3. Note that any vertex cover will have to contain at least two vertices from V_j' to cover the edges of E_j'.
For c_j in F let the three literals in c_j be denoted by y_j, z_j, w_j. So c_j = (y_j \lor z_j \lor w_j). The communication edges for S_j are E_j'' = \{\{a_1(j), y_j\}, \{a_2(j), z_j\}, \{a_3(j), w_j\}\}. Out instance of VC is G = (V, E) where V = \bigcup_{i=1}^nV_i \cup \bigcup_{j=1}^m V_j' and E = \bigcup_{i=1}^n E_i \cup \bigcup_{j=1}^m E_j' \cup \bigcup_{j=1}^m E_j'' and k = n + 2m.
One can see that (G, k) can be constructed in polynomial time.
F is satisfiable \iff G has a vertex cover of cardinality \le k.
\impliedby Suppose that W \subseteq V is a vertex cover of G and |W| \le k. By our previous remarks W has to contain at least one vertex from every T_i and at least two vertices from every S_j. Since it gives a total of at least n + 2m = k vertices, |W| = k and W must contain exactly one vertex from every T_i and exactly two vertices from every S_j. We use the vertices of W contained in T_is to define an assignment V: X \to \{0, 1\}. We set v(x_i) = 1 if x_i \in W and v(x_i) = 0 otherwise. We will show that v satisfies every clause c_j in F. Consider three communication edges in E''_j. Only two of these edges can be covered by vertices from V_j' \cap W, so one of them must be covered by a vertex from V_i \cap W for some i. But that implies that the corresponding literal (x_i or \neg x_i) is true under assignment v, so c_j is satisfied by v. Because it holds for every clause c_j in F, v is a satisfying assignment for F.
\implies Suppose that v: X \to \{0, 1\} is a satisfying assignment for F. THe corresponding vertex cover W will contain one vertex from every T_i and two vertices from every S_j (n + 2m = k \le k vertices). The vertex from T_i in W is x_i if v(x_i) = 1 and \neg x_i otherwise. This ensures that at least one of the three edges in every E''_j is covered, because v satisfies every clause c_j. Therefore we need to include in W the ends in V'_j of the other two edges from E_j'' (which may or may not be also covered by vertices from T_is. \square
A non-deterministic algorithm guesses a permutation of the vertices and checks in polynomial time whether it is a hamiltonian cycle.
Let G = (V, E) and k \in N be an instance of VC. we will construct a graph G'=(V', E') such that G contains a vertex cover of cardinality \le k \iff G' has a hamiltonian cycle.
Components: selector vertices + cover testing components + communication edges
G' will contain k selector vertices S = \{a_1, \cdots, a_k\}.
For every edge e = \{u, v\} \in E there is a cover testing component C_e = (V_e', E_e') where V_e' = \{(u, e, i), (v, e, i) : 1 \le i \le 6\} and E'_e = \{\{(u, e, i), (u, e, i+1)\}, \{(v, e, i), (v, e, i+1)\}: 1 \le i \le 5\} \cup \{\{(u, e, 3), (v, e, 1)\}, \{(v, e, 3), (u, e, 1)\}, \{(u, e, 6), (v, e, 4)\}, \{(v, e, 6), (u, e, 4)\}\}.
In the completed construction only vertices of this component that will be incident with communication edges are (u, e, 1), (u, e, 6), (v, e, 1), (v, e, 6). Any Hamiltonian cycle in G' will have to traverse this cover testing component in exactly one of three configuration. For every vertex v \in V let the edges incident with v be ordered (arbitrarily) as e_{v(1)}, e_{v(2)}, \cdots, e_{v(d(v))} where d(v) = degree of v. All the cover testing components corresponding to these edges are joined with the following communication edges E_v' = \{\{(v, e_{v(i)}, 6), (v, e_{v(i+1)}, 1)\}: 1 \le i < d(v)\}. The final communication edges join the ends of these paths to every one of the selector vertices. These are the following edges E'' = \{\{a_i, (v, e_{v(1)}, 1)\}, \{a_i, (v, e_{d(v)}, 6)\}: 1 \le i \le k, v \in V\}. Our instance of HC is G'=(V', E') where V' = S \cup \bigcup_{e \in E} V_e' and E' = \bigcup_{e \in E} E_e' \cup \bigcup_{v \in V} E_v' \cup E''. One can see that we can construct G' from G and k in polynomial time.
G has a vertex cover of cardinality \le k \iff G' has a Hamiltonian cycle.
\impliedby Suppose v_1, v_2, \cdots, v_n, v_1 where n = |V'| is a Hamiltonian cycle in G'. Consider any minimal subpath of the cycle that begins and ends in a vertex from S. Because of the previously described restrictions on the way in which the Hamiltonian cycle can pass through a cover testing component, this fragment of our cycle must pass through a set of cover testing components corresponding to exactly these edges from E which are incident with some one particular vertex v \in V. Each of the cover testing components is traversed in one of the three ways and no vertex from any other cover testing component is visited. Thus the k selector vertices divide our Hamiltonian cycle into k paths, each path corresponding to a different vertex v \in V. Since the Hamiltonian cycle must visit all vertices from all cover testing components and since vertices from the cover testing component corresponding to and edge e \in E can be traversed only by a path corresponding to one of the ends of e, every edge e \in E must have at least one end among those selected vertices from V. Therefore this set of k vertices forms a vertex cover of G.
\implies Suppose W \subseteq V is a vertex cover of G and |W| \le k. We can assume that |W| = k (otherwise we can just add some vertices to W). We choose the edges of a Hamiltonian cycle in G'. From the cover testing components corresponding to the edge \{u, v\} \in E we choose the edges specified by (a), (b), or (c) depending on whether \{u, v\} \cap W equals \{u\}, \{u, v\}, or \{v\} respectively, one of those must occur because W is a vertex cover of G. Next we choose the edges in E_{v_i}' for 1 \le i \le k. Finally we choose the edges \{\{a_i, (v_i, e_{v_i(1)}, 1)\}: 1 \le i \le k\}, \{\{a_{i+1}, (v_i, e_{v_i(d(v_i))}, 6)\}: 1 \le i < k\}, and \{a_1, (v_k, e_{v_k(d(v_k))}, 6)\}. The subgraph of G' induced by these edges is a hamiltonian cycle.
A non-deterministic algorithm guesses a permutation of vertices and checks in polynomial time if the sum of weights of the corresponding Hamiltonian cycle is \le b.
A non-deterministic algorithm guesses a subset of vertices and checks in polynomial time whether this subset is a dominating set and has cardinality \le k.
Let G = (V, E), k be an instance of VC. We will construct an instance G' = (V', E'), k' of DS such that G has a vertex cover of cardinality \le k \iff G' has a dominating set of cardinality \le k'. For every edge uv \in E let w_{uv} be a new vertex. Let V' = V \cup \{w_{uv} : uv \in E\}, E' = E \cup \{uw_{uv}, w_{uv}v : uv \in E\} and k' = k. G' and k' can be constructed from G, k in polynomial time.
G has a vertex cover of cardinality \le k \iff G' has a dominating set of cardinality \le k'
\implies Suppose W \subseteq V is a vertex cover of G and |W| \le k. W is a dominating set in G'.
\impliedby Suppose W' \subseteq V' is a dominating set of G' and |W'| \le k' = k. We run the following procedure:
Then W \subseteq V is a vertex cover of G and |W| \le |W'| \le k
\Sigma = \{a_1, \cdots, a_k\} - a language. RAM has an infinite set of registers R1, R2, \cdots. Each register stores a string from \Sigma^*. There is an infinite set of line names N1, N2, \cdots. There are 7 types of instructions: N1 - a line name or nothing, RX, RY - registers. N2' \in \{N2a, N2b\} (a - above, b - below).
Instructions are executed in order in which they are written except jumps.
A RAM program is a finite sequence of instructions such that each jump is executable and the last instruction is continue. A RAM program halts when it reaches the final continue instruction.
A partial function f: N^n \to N is computable on RAM if there exists a RAM program P such that if it starts in the following configuration: for i = 1, \cdots, n x_i is in R_i and all the other registers are empty (\varepsilon) and:
Lemma: Instructions 3,4,5 can be eliminated from the set of instructions.
Suppose RAM program P uses only the registers R1, \cdots, Rm. Before the execution of P, Ri contains string r_i for all i. P consists only of instructions of type 1, 2, 6, or 7. We assume P contains only one instruction of type 7. Construction of a TM M simulating P:
Let n be the number of instructions of P. M consists of n blocks - each block corresponds to one instruction of P. Blocks are joined in a way that the instructions of P will be executed in the same order as in P. On the input M has r_1, r_2, \cdots, r_m on the tape (commas are in the string).
Let M = (Q, \Sigma, \Gamma, \delta, B, q_1, F). Let Q = \{q_1, \cdots, q_s\}. Let m = |\Gamma| + 1. We encode the symbols from \Gamma with 0, 1, \cdots, m-1 in a way that B is encoded with 0 and m-1 is the code of a special end of tape symbol. We construct a RAM program P that simulates the computation of M. P will use three registers R\text{-}1 (string before the head), R0 (character under the head), R1 (string after the head). b_i is the code of the symbol in i-th cell.
P:
[read input string and initialize the registers]
N1 [moves of M from the state q_1]
N2 [moves of M from the state q_2]
\vdots
Ns [moves of M from the state q_s]
Each Nj:
R0 jmp0 Nj,0b
R0 jmp1 Nj,1b
...
R0 jmpm-2 Nj,m-2bI give up