Računska zahtevnost (Cabello)
Warning: The notes are not optimized for HTML (yet). Without warranty.
Lecture 1: Motivation
For a matrix \(A \in \R^{n \times n}\) we usually define a determinant as \[ \det(A) = \sum\limits_{\sigma} \sgn(\sigma) . \prod\limits_{i \in [n]} a_{i, \sigma(i)}. \]
Looking at it as a computational problem that inputs the matrix \(A\) and outputs the determinant \(\det(A)\). How quickly can we compute it?
- We can compute it in \(O(n!)\) time by directly applying the definition. Using the stirling approximation, this is something like \(O(\sqrt{2\pi n} (\frac{n}{e})^n)\) time, which is very inefficient.
- Using Gaussian elimination \(A = LUP\), we can compute the determinant as \(\det(A) = \det(L) \cdot \det(U) \cdot \det(P)\). We have \(O(n^3)\).
- We can compute it in \(O(n^{\omega})\) time by using fast matrix multiplication algorithms, where \(\omega < 2.375\).
This gives us a general view of what happens.
- The reduction from step 1 to 2 is significant, we go from superexponential to a polynomial algorithm.
- When we get a polynomial time algorithm, we try to reduce it as much as possible.
- We cannot get linear time, since the input is itself quadratic.
- For \(O(n^2)\), we do not know.
- But we have a state of the art solution in \(O(n^{2.375})\).
There's a problem with the example though. The \(O(n^3)\) talks about sums and products, which are nonconstant as time goes on. Choosing the pivot carefully, we can get polynomial time, but it can be much greater.
We can fix this by taking a finite field, say \(\Z_7\). There's fundamentally more informations as \(n\) grows. Picking a finite field is a common "hack".
We should be careful with this. Nobody is careful with this.
\[ \operatorname{perm}(A) = \sum\limits_{\sigma} \prod\limits_{i \in [n]} a_{i, \sigma(i)} \]
This is an analogous problem which can again be computed by definition which is again computable in \(O(n!)\). But here we do not know of a polynomial time algorithm.
- For instance, the permanent of a \(\Z_2\) matrix is the number of perfect matchings in a bipartite graph.
- Note that we can compute a single perfect matching in a bipartite graph (optimisation methods/linear programming).
- We do not know how to count such matchings in polynomial time.
- Can we generate a perfect matching uniformly at random in the set of perfect matchings in a bipartite graph? We again do not know how to do it in polynomial time.
The naive algorithm checks divisors up to \(n\) (or up to \(\sqrt{n}\)). Assuming that checking \(i \mid n\) takes constant time, this would give us \(\approx\sqrt{n}\) steps.
Here's a trap. It's polynomial in \(n\), but not polynomial in \(\log_2(n)\). The more correct size of the input is the number of digits. Then \(\sqrt{n} \approx 2^{\frac{1}{2}\log_2n}\), which is exponential in the input size.
Since the 70s, it is known that we have a \(\log_2n\) polynomial time algorithm that tests primality with high probability, where there are no false positives, but might be false negatives, i.e. it might say a composite number is prime with probability \(\leq \frac{1}{4}\). This is in randomized polynomial time. To improve the odds, we can rerun the algorithm repeatedly.
In 2002, Aggraval, Kayal, Sexena showed there exists a deterministic polynomial time algorithm which recognises prime numbers.
For a natural number, return a number that divides it or mark it prime.
We do not know how to factorize in polynomial time (deterministic or rational).
- If problem \(A\) can be solved in polynomial time, then problem \(B\) can be solved in polynomial time. (Reduction)
- If we have sets of problems with some given properties \(X, Y\), we're looking at \(X \subseteq Y\) or \(X = Y\).
- Problem \(X\) needs at least time/space \(\approx n^2\), say. (Lower bound)
The lower bound problems are very very few, and usually very weak.
Lecture 2: Basic definitions
If we have integers \(a, b\) of length \(n\), we learned in primary school to add them in \(O(n)\) and multiplying them in \(O(n^2)\). In fact, we can get multiplication down to \(O(n\log n)\) using a galactic algorithm. Even so, using FFT, we have more practical algorithms of \(O(n \log^2 n)\).
Still, we do not know if this \(\log\) factor is required and multiplication really is more computationally demanding.
An encoding is a function \[ e : \text{ inputs} \rightarrow \left\{ 0, 1 \right\}^{ * }. \]
(We could use some other alphabet, but we use binary encodings on the computer.)
We assume a fixed explicit encodings in this course. This means that we always have an explicit input, e.g. we could give a number recursively in terms of its digits, but we still always assume it to be given explicitly.
A computational problem with boolean output.
The fiber of true becomes interesting as an object of study. When we view it in an encoding, it is \[ L = \left\{ w \in \left\{ 0, 1 \right\}^{ * } \mid P(w) \right\} , \] which is a language. So decision problems are recognising a language. (For now?) we only care about decidable languages.
An additional detail to sweep under the rug is that we assume \(P(w)\) also checks the validity of \(w\), i.e. we never think about encoding problems as such.
\[ \begin{aligned} f &= O(g(n)) \iff \exists C \in \R .\exists n_0 \in \N . \forall n \geq n_0 . f(n) \leq C \cdot g(n) \\ f &= \Omega(g) \iff g = O(f) \\ f &= \Theta(g) \iff f = O(g) \text{ in } g = O(f) \end{aligned} \] We also use the little \(o\) notation, which indicates a weak upper bound: \[ f = o(g) \iff \exists n_0 \in \N . \forall C > 0 . \forall n \geq n_0 . f(n) \leq C g(n) \] i.e. all since we have enough additional complexity, it dominates any constant. We get \[ f = o(g) \implies \lim_{n \rightarrow \infty} \frac{f}{g} = 0 \]
Likewise we define \[ f = \omega(g) \iff g = o(f). \]
For computational complexity, we want an explicit notion of time and space, which is better done in Turing machines than, say, \(\lambda\)-calculus. The definiton is very robust - we have several equivalent variants we can deploy when need be.
We define it as \((\Gamma, \sqcup, Q, q_s, q_h, \delta)\) where \(\delta : \Gamma \times Q \rightarrow \Gamma \times Q \times \left\{ -1, 0, 1 \right\}\) is the transition function.
The definition of the TM doesn't itself speak of the tape state. We also define a configuration of the TM \(M\) as \((q, t, i)\) where \(q\) is the state of the control unit, \(t : \Z \rightarrow \Gamma\) the state of the tape and \(i \in \Z\) the position of the head. The initial configuration is then \((q_s, in, 0)\). The input is always right from 0.
A TM \(M\) recognizes a language \(L\) if
- For every input, \(M\) halts
- \(\forall \omega \in L .\,\) applying \(M\) to \(\omega\) finishes with \(q_{\text{accept}}\)
- \(\forall \omega \not\in L .\,\) applying \(M\) to \(\omega\) finishes with \(q_{\text{reject}}\)
There exist undecidable languages.
An example is the halting problem.
- Input: a Turing machine \(M\) and \(\omega\).
- Output: Does the Turing machine \(M\) with input \(\omega\) halt?
Another example is Hilbert's 10th problem:
- Input: A polynomial with multiple variables and coefficients in \(\Z\).
- Output: Does the polynomial have a zero in \(\Z\)?
Let \(M\) be a TM. We define
\begin{align*} \operatorname{time} : {\N} &\rightarrow \N \cup \left\{ \infty \right\} \\ n &\mapsto \text{ maximum time that \(M\) runs over all inputs of length \(n\)} \end{align*}Note: A Turing machine has time complexity \(O(n)\) or \(\Omega(n \log n)\). We cannot have something like \(\Theta(n \sqrt{\log n})\).
It computes a function \[ f : \Sigma_1^{ * } \rightarrow \Sigma_2^{ * } \] if
- \(M\) always finishes for \(\omega \in \Sigma_1^{ * }\)
- \(M\) has a halting state \(q_{h}\)
- At the end the tape contains \(f(\omega)\) and all blanks around.
In particular this means we need \(\Gamma \supseteq \Sigma_1 \cup \Sigma_2 \) .
This is more general than decideability, which reduces to the case \(f : \Sigma^{ * } \rightarrow \left\{ 0, 1 \right\}\).
\(M\) computes a function \(f : \left\{ 0, 1 \right\}^{ * }\) in time \(\operatorname{time}_M(n)\) using \(\abs{\Gamma} = k\) symbols. Then there exists another TM \(\widetilde{M}\) that computes \(f\) which uses symbols \(\widetilde{\Gamma} = \left\{ 0, 1, \sqcup \right\}\) and has time complexity \[ \operatorname{time}_{\widetilde{M}}(n) = O(\operatorname{time}_M(n) + n^2). \] Note that the \(O\) constant depends on the original TM.
The idea is that we define and use an injection encoding all original symbols (including blank) \[ \Gamma \hookrightarrow \left\{ 0, 1, \sqcup \right\}^{k} \] where we encode each symbol as a \(k\)-chunk. \(\widetilde{Q}\) records partial readings for blocks. One step of \(M\) becomes \(O(k)\) steps of \(\widetilde{M}\).
The \(O(n^2)\) term comes only from copying the data.
Lecture 3: Deterministic Turing Machines
A \(k\)-tape Turing machine has \(k\) tapes. It's equivalent to consider transition functions which move just one or all tape-heads at once. Sometimes one of the tapes is considered to be read-only and considered as an input tape, likewise sometimes we only have an output tape, etc.
If there exists a TM with \(k\) tapes that recognizes \(L\) in time \(T(n)\), then there exists a 1-tape TM that recognizes \(L\) in time \[ O(T(n)^2). \]
In particular, if \(k\)-tape \(M\) runs in polynomial time, so does the 1 tape version.
The idea is that we intercalate the tapes. Use states to remember from which tape of \(M\) we are reading in \(\widetilde{M}\).
The new set of symbols for \(\widetilde{M}\) is \[ \widetilde{\Gamma} = \Gamma \cup \left\{ \widehat{a} \mid a \in \Gamma \right\} \] where the symbol \(\widehat{a}\) in the tape indicates the head of the given tape is there.
We get \(\widetilde{Q} = Q \times \widehat{\Gamma}^k \times [k] \cup O(1) \text{ states}\)
This is a data-oblivious construction, we access the data following the same pattern, independent of the actual data. The quadratic term comes from the fact we need to read the whole tape on each step.
Same idea as the bijection \(\N \cong \Z\). Or store pairs and use \(\Gamma^2\).
Whenever there exists a TM \(M\) of some type that recognizes a language \(L\), there exists another \(TM\) \(\widetilde{M}\) of some other type that recognizes \(L\). Moreover, \[ \operatorname{time}_{\widetilde{M}}(n) = O\left((\operatorname{time}_M(n))^{\text{constant}}\right) \]
We say that \(\operatorname{DTIME}(f(n))\) is the set of languages \(L\) such that there exists a TM \(M\) that recognizes \(L\) and has \[ \operatorname{time}_M(n) = O(f(n)). \]
We usually take the \(TM\) to be a \(k\)-tape machine for some constant \(k\).
This is a non-robust definition.
We define \[ \operatorname{P} = \bigcup\limits_{d \geq 1} \operatorname{DTIME}(n^d). \]
A problem \(\in \operatorname{P}\) is
- A decision problem
- that can be recognized in polynomial time
Note that \(\operatorname{P}\) is a natural definition.
- Constants are not relevant. For instance, we can get constant speed-up using more symbols.
- It's robust wrt the type of the TM.
- Computers, contra TMs, have (finite) RAM.
- This ends up making no difference, we can simulate indexed access using a TM (with quadratic blowup), using counters.
- \(\operatorname{P}\) is closed wrt to taking calls to other programs in \(\operatorname{P}\) that do not grow the output. An issue would be a program which doubles the input.
- Currently, all of the physically realizable notions of computation give the same definition of polynomial time.
We define \[ \operatorname{EXP} = \bigcup\limits_{d \geq 1} \operatorname{DTIME} \left( 2^{n^{d}} \right) \]
\[ \operatorname{P} \subseteq \operatorname{QuasiP} \subset \operatorname{EXP}. \] In general these are strict inclusions, but we do not know that yet at this point in the course.
An Universal Turing machine is a TM \(\mathcal{U}\) that takes as input \(\left< M, x \right>\), where \(M\) is (a description of) a Turing machine, \(x\) is an input word to \(M\), and returns \(M(x)\), i.e. what the TM \(M\) would give for input \(x\).
Furthermore, \(\mathcal{U}\) simulates the computation of \(M(x)\).
Notes:
- The universal TM corresponds to an interpreter.
- \(\mathcal{U}\) can have a fixed number of symbols and states but can simulate arbitrary TMs.
- Universal TMs exist and can simulate \(M(x)\) efficiently. We can do it with quadratic blowup with 1 tape. With multiple tapes, we can get the blowup down to \(n \log n\).
Lecture 4: Nondeterministic computing
A nondeterministic Turing machine with 1 tape has transition function \[ \delta : Q \times \Gamma \rightarrow \pot(Q\times \Gamma \times \left\{ 0, -1, 1 \right\}) \] which maps a state to a set of states, corresponding to the options of the next state. Note that we have no explicit choice over the branching.
A Nondeterministic Turing machine accepts a language \(L\) if
- It always finishes its computation
- If \(\omega \in L\), there must exist a computation path that finishes with \(q_{\text{accept}}\).
- If \(\omega \not\in L\), all possible branches must finish with \(q_{\text{reject}}\).
Let \(M\) be a NTM. Then
\begin{align*} \operatorname{time}_M(n) = &\text{ max of the number of steps of all inputs of size } \\ &n \text{ and over all possible choices made non-deterministically} \end{align*}Our definition takes the maximum over all inputs and choices. One can also take the definition where we take the minimum over the choices, but we must be more careful in this instance. For time complexity, both definitions are equivalent - we can always add a counter and keep track of the steps and memory.
We also have a time complexity class for nondeterministic Turing machines.
\[ \operatorname{NP} = \bigcup\limits_{d \geq 1} \operatorname{NTIME}(n^d). \] This is the decision problems for which there exists a NTM \(M\) that solves the problem in \(O(n^d)\) for some constant \(d \leq 1\).
Note that \(\operatorname{P} \subseteq \operatorname{NP}\), since a deterministic TM is also a nondeterministic TM.
A big question of computability is whether \(\operatorname{P} = \operatorname{NP}\). It is thought to be an inequality, but we do not know how to approach the problem.
\(L \in \operatorname{NP}\) if and only if there exists a polynomial time deterministic TM \(M\) and a polynomial \(p\) such that \[ \forall x \in \left\{ 0, 1 \right\}^{ * } .\, x \in L \iff \exists y \in \left\{ 0, 1 \right\}^{p(\abs{x})} .\, M(x, y) = 1, \] i.e. \(M\) accepts \((x, y)\). We call \(y\) a certificate for \(x\).
Note that if the answer is no, there exists no certificate. This means any possible certificate we take will reject.
The idea is that we can take \(y\) to be the encoding of the choices made by the machine.
\((\implies)\): Let \(L \in \operatorname{NP}\). There exists a NTM \(M\) that runs in polynomial time \(\operatorname{time}_M(n) = q(n)\). Then \[ x \in L \iff \text{ a computation path accepts } x \] We design a deterministic TM \(\widetilde{M}\) that has one extension tape \(T\). In the new tape, we write an encoding of the choices made by \(M\) to accept \(x\). We take what is written as \(y\). For \(\widetilde{M}\) we make a deterministic transition function that uses the tape \(T\) as additional input which \(\widetilde{M}\) consults to collapse the choice of next state.
When \(M\) rejects \(x\), all computation paths lead to rejection, so in particular every \(y\) written in \(T\) leads to rejection in \(\widetilde{M}\).
- \(\impliedby\): Say there exists a TM \(M\) with the desired properties and polynomial time complexity. Thus \[ x \in L \iff \text{ a computation path accepts } x. \] We define the nondeterministic TM to write \(y\). This means we have \(2^{p(n)}\) options for computation paths. We use a counter to keep track of how much of the certificate we have written. NB that we took the certificate to always be of the length \(p(\abs{x})\). Then after writing out \(y\), we run our \(M(x,y)\). In the branch where \(M(x, y) = 1\), \(\widetilde{M}\) accepts \(x\).
An example of a problem in \(\operatorname{NP}\) is computing the independent set. We take a graph \(G\) and \(k \in \N\) as an input and we're computing a set \(U \subseteq V(G)\) such that \(\abs{U} \geq k\) such that \[ \not\exists u, v \in E(G) . \, \left\{ u, v \right\} \subseteq U \]
A certificate in this case is a \(U \subseteq V(G)\) that satisfies the condition.
FINISH Lecture 5:
Cooks-Levin's theorem
…
\[ \phi_6(w) = \phi_6^1(w) \land \phi^2_6(w) \]
- \(\phi_6^1\) means? no changes in places of the tape where the head is not reading.
- \(\phi_6^2\) tracks? changes of state, symbol (where the head is reading) and movement.
\[ \phi_6^1(w) = \bigwedge_{j=0}^{q(\abs{w})} \bigwedge_{i = -(\abs{w})}^{q(\abs{w})} \bigwedge_{a \in \Gamma} \left( \neg x_{i, j, a} \lor y_{i, j} \lor x_{i, j+1, a} \right) \] We read this as \[ (x_{i,j,a} \land \neg y_{i, j}) \rightarrow x_{i, j+1, a} \] since \(p \lor q \equiv \neg p \rightarrow q\). \[ \phi_6^2(w) = \bigwedge_{j=0}^{q(\abs{w})} \bigwedge_{i = -q(\abs{w})}^{q(\abs{w})} \bigwedge_{q \in Q} \bigwedge_{a \in \Gamma} \left( \left( \underbrace{\neg y_{i, j} \lor \neg z_{j, q} \lor x_{i, j, a}}_{ * } \lor y_{i + \Delta(q, s), j + 1} \right) \land ( * \lor z_{j + 1, \widetilde{q}(q, a)}) \land ( * \lor x_{i, j + 1, b(q, a)}) \right) \] where \[ \delta(q, a) = (b(q, a), \widetilde{q}(q, a), \Delta(q, a)) \] is the transition function for the new state.
Again we read this as \[ (y_{i, j} \land z_{j, q} \land x_{i, j, a}) \rightarrow y_{i + \Delta(q, a), j+1}. \]
- For a given input and fixed certificate the variables tell you (???) - if you can finish with a true, the certificate exists, otherwise the certificate does not exist
- Reading \(x_{i, 0, a}\) with \(i = \abs{w}, \dots, \abs{w} + p(\abs{w})\) we set a certificate, if it exists.
- The size of \(\phi(w)\) is polynomial in \(\abs{w} = n\).
- Given \(w\), we can compute/construct \(\phi(w)\) in polynomial time.
- Given a NTM or TM+certificate with bounds \(p(n)\) and \(q(n)\) for the certificate and time respectively, that recognizes a language \(L \in \text{NP}\), then we have shown that there exists a function \[ f : 2^{ * } \rightarrow 2^{ * } \] where \(f(w)\) can be computed in polynomial time for each \(w\). Then \[ w \in L \iff f(w) \in \text{SAT}. \]
Lecture 6:
The state of our knowledge is that
- SAT is NP-complete.
- If \(L\) is NP-complete, \(L' \in \text{ NP}\) and \(L \leq_p L'\), then \(L'\) is NP-complete.
- For instance, \(\text{SAT} \leq_q 3-\text{SAT}\), so we must have that 3-SAT is NP-complete.
More examples of NP complete problems
- Independent set is NP complete (exercises)
- CLIQUE is NP-complete:
- VERTEX COVER is NP-complete.
- 3-COLORABILITY
CLIQUE
- Input: \(G\) graph, number \(k\)
- Output: \(\exists U \subseteq V(G)\) where \(\abs{U} = k\) such that \(\forall u, v \in U.\, u \neq v . \, uv \in E(G)\).
CLIQUE is NP-complete.
\(U \subseteq V(G)\) is a clique \(\iff U\) is independent in \(\overline{G}\).
Warning: If we look at a \(n\)-clique problem, say 100-clique, asking does \(G\) have a clique of size 100 belongs to P. If we fix the number we're in the realm of parametrized complexity.
VERTEX COVER
- Input: A graph \(G\) and number \(k\).
- Output: \(\exists U \subseteq V(G).\, \(\abs{U} = k\) such that \(\forall uv \in E(g) .\, \left\{ u, v \right\} \cap U \neq \emptyset\)
VERTEX COVER is likewise NP-complete
\(U\) is a clique in \(G \iff U\) is an independent set in \(\overline{G} \iff V(G) \setminus U\) is a vertex cover in \(\overline{G}\).
Let \(U\) be an independent set in \(H = \overline{G}\). Then \(V(G) \setminus U\) is a vertex cover in \(H\), i.e. \[ \forall uv \in E(G).\, u \not\in U \lor v \not\in U \iff u \in V(G) \setminus U \lor v \in V(G) \setminus U. \] Thus we have a polynomial time reduction from the independent set to the vertex cover problem
3-COLORABILITY
- Input: Graph \(G = (V, E)\)
- Output: \(\exists c : V \rightarrow \left\{ R, G, B \right\}\) such that \(\forall uv \in E .\, c(u) \neq c(v)\).
TSP (travelling salesperson problem)
- Input: Graph \(G\) with positive edge weights (representing distances) \(w : E \rightarrow \R_{+}\) and \(L > 0\).
- Question: Does there exist a closed walk \(W\) visiting all vertices with total weight at most \(L\).
Another version of the problem asks us about \(n\) cities and a distance matrix between each two cities. We are interested in a permutation \(\sigma : [n] \rightarrow [n]\) where \(\sum\limits_{i\in[n]} D_{\sigma(i), \sigma(i+1)} \leq L \).
TSP is NP-complete.
It is in NP since we can give the walk explicitly. It is NP-hard since we can reduce the hamiltonian problem to it.
SUBSET SUM
n(Also called 0-1 knapsack)
- Input: \(a_1, \dots a_n \in \N\) and \(B\in \N\).
- Question: Is there a subset of the indices of the given numbers such that its sum adds up to \(B\).
SUBSET SUM is NP-complete.
It is obviously in NP.
We will show it is NP-hard by showing \(\text{VERTEX COVER} \leq_p \text{SUBSET SUM}\).
Recall that vertex cover a subset of the graph nodes which touches all the edges of \(G\). We want to select \(k\) "stars" in \(G\) that cover all edges. Each edge is covered once or twice. We use characteristic vectors indexed by edges. Let \(e_1, e_2, \dots, e_{m}\) be an enumeration of edges and \(v_1, \dots, v_n\) an enumeration of the vertices. We write that as a matrix
\[
\begin{matrix} & \text{c} & e_1 & e_2 & e_3 & e_4 & \dots & e_m \\ v_1 & 1 & 0 & 1 & 1 & 0 & \dots & 0 \\ \vdots & \vdots \\ v_n & 1\\ e_1 & 0& 1 \\ e_2 & 0& & 1 \\ \vdots & \vdots\\ e_m & 0& & & & & & 1 \\ B & k & 2 & 2 &\cdots \end{matrix}\]
where we have exactly one 1 in position \(e_j\) for \(e_j\) at the bottom and as many 1s as \(\deg(v_i)\) in the upper part. The counter column is 1 for vertices and 0 for edges.
The reduction is as follows. For each edge, enumerate the vertices \(v_1, \dots, v_n\) and the edges \(e_1, \dots, e_m\). For every vertex \(v_i\) we make the number \[ a_i = 10^{m} + \sum\limits_{\overset{j \in [m]}{v_i \text{ endpoint of } e_j}} 10^{j - 1} \] for each edge \(e_j\) we make the number \(b_j = 10^{j - 1}\). Define \[ B = k \cdot 10^m + \sum\limits_{j \in [m]} 2 \cdot 10^{j-1}. \] The resulting instance for SUBSET SUM is \[ f(G, k) = \left( \left\{ a_1, \dots, a_n, b_1, \dots b_m \right\}, B \right). \] Assume \((G, k)\) has a vertex cover \(U\) of size \(k\). Let \(I \subseteq [n]\) be such that \(\left\{ v_i \mid i \in I \right\} = U\). Then \[ \sum\limits_{i \in I} a_i = k \cdot 10^m + \sum\limits_{j \in [n]} (1 \text{ or } 2) \cdot 10^{j - 1}. \] Define \(J = \left\{ j \in [m] \mid e_j \text{ has exactly one endpoint in } U \right\}\).
Then \[ \sum\limits_{i \in I} a_i + \sum\limits_{j \in J} b_j = k \cdot 10^m + \sum\limits_{j \in [n]} 2 \cdot 10^{j-1} = B. \] Therefore \(f(G, k)\) has a solution.
The other direction. Assume \(f(G, k)\) has a solution. Let \(I \subseteq [n]\)and \(J \subseteq [m]\) define a solution. Thus \[ \sum\limits_{i \in I} a_i + \sum\limits_{j \in J} b_j = B. \] We claim that \(\left\{ v_i \mid i \in I \right\}\) is a solution for \((G, k)\). In the rightmost \(m\) digits of the sum there is no carrying (in base 10) therefore there is no carrying in the digits of the sum there are at most three 1. Therefore, \[ \sum\limits_{i \in I} a_i = \abs{I} \cdot 10^m + \sum\limits_{j \in [m]} (1 \text{ or } 2) \cdot 10^{j - 1}. \] Thus \(\left\{ v_i \mid i \in I \right\}\) is a vertex cover in \(G\) of size \(\abs{I}\). Because \(\abs{I} \cdot 10^m = k \cdot 10^m\), the set \(\left\{ v_i \mid i \in I \right\}\) has \(k\) elements.
We had to be careful with the reduction. Had we used base 2, we would have had a problem in the other direction.
Lecture X: Space complexity introduction
We measure how much working space a TM (deterministic or not) uses. Working space is given as the number of position in tapes that are used excluding a tape for read-only input and a tape for write-only output. The output tape is relevant only when computing functions, irrelevant for decision problems.
For a TM \(M\) (deterministic or nondeterministic) we define \[ \operatorname{space}_{M}(n) = \max{S_n} \] where \(S_n\) contains the number of positions in working tapes used on inputs of size \(\leq n\) over all possible runs of the machine \(M\).
\noindent Counting all the runs is relevant when it comes to nondeterministic machines.
which we call polynomial space and nondeterministic polynomial space respectively.
We also define
\begin{align*} \operatorname{L} &= \operatorname{PSPACE}(\log n) \\ \operatorname{NL} &= \operatorname{NPSPACE}(\log n) \end{align*}which we call logarithmic and nondeterministic logarithmic space. These form examples of sublinear space complexity.
\noindent Can a univeral TM simulate a TM that runs in \(S(n)\) space in \(O(S(n))\) space? Note that this did not work in time complexity. But here the idea is that you can reuse space, but cannot reuse time.
\(\operatorname{NP} \subseteq \operatorname{PSPACE}\)
\leavevmode
- Let \(L \in \operatorname{NP}\). Then we have a polynomial \(p(n)\) and a TM \(M\) that runs in polynomial time. This in particular means it must run in polynomial space. We laso have \[ x \in L \iff \exists u \in \{0, 1\}^{\leq p(\abs{x})} \text{ such that } M(x, u) = 1 \] Try each \(u \in \left\{ 0, 1 \right\}^{\leq p(x)}\) reusing the space. The space we use is \(\operatorname{space}(M(x, u)) + \text{ the space for } (u) \leq \operatorname{poly}(\abs{x})\).
- For any \(L \in \operatorname{NP}\), we have that \(L \leq_p \operatorname{SAT}\). The reduction showing \(L \leq_p \operatorname{SAT}\) uses polynomial space. Thus it suffices to show that \(\operatorname{SAT} \in \operatorname{PSPACE}\). But this holds because we can simply try all variable assignments.
\[ \operatorname{NPSPACE} \subseteq \operatorname{EXP} \]
Consider any \(L \in \operatorname{NPSPACE}\). This means there exists a NTM \(M\) that runs in space \(O(n^d)\) and recognizes \(L\). A configuration is given by:
- The state of the machine \(M\) where \(\abs{Q} = O(1)\)
- What is written in the tape, which has complexity \(\abs{\Gamma}^{O(n^d)}\)
- The position of the head, of complexity \(O(n^d)\).
The \(O(n^d)\) have a factor of 2x hidden, since we can have spaces in both directions. Let us estimate the bits to encode a configuration. \[ O(1) + \underbrace{\log(\Gamma^{O(n^d)})}_{O(n^d)} + \underbrace{\log O(n^d)}_{\leq O(n^d)} = O(n^d). \]
We build a graph \(G = G(M, x)\) where the nodes are (encodings of) configurations and directed edges \(C \rightarrow C'\) represent if \(M\) can transform \(C\) to \(C'\) in one step of \(M\). The number of nodes is \(2^{O(n^d)}\). There exists a starting configuration encoding state \(q_{\text{start}}\), an encoding of \(x\) in the input tape and head in position 1. We add a node YES and add directed edges from all accepting configurations to YES. We have to decide when a path in \(G\) from the starting configuration to YES exists. We can do this using BFS or DFS or the like.
The number of edges of this graph is \(\left( 2^{O(n^d)} \right)^2 = 2^{O(n^d)}\). The algorithm takes time \(2^{O(n^d)}\) and thus \(L \in \operatorname{EXP}\).
The same idea shows that we have \(\operatorname{NL} \subseteq \operatorname{P}\).
This is because \[ 2^{O(\log n)} \leq 2^{C \cdot \log_2 n} = n^c. \]
QBF - Quantified Boolean formulas
So far we have \[ \mathrm{L} \subseteq \mathrm{NL} \subseteq \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} \subseteq \mathrm{NPSPACE} \subseteq \mathrm{EXP} \subseteq \mathrm{NEXP} \] We know that
- P is strictly contained in EXP (By the Time Hierarchy theorem)
- L is strictly contained in PSPACE (Space Hierarchy theorem, which we did not see)
Today we will show that \(\mathrm{PSPACE} = \mathrm{NPSPACE}\). We will do this by looking at quantified boolean formulas
In SAT, we get as input formula \(\phi\) in CNF. We are looking for an assignment of binary values to the variables that make the formula true. More precisely, we have a input \(\phi(x_1, \dots, x_n )\) and the question whether \[ \exists x_1 .\, \exists x_2 .\,\dots \exists x_n .\, \phi(x_1, \dots, x_n). \] QBF generalises this to arbitrary quantifiers.
When dealing with quantified boolean formulas, we have a formula of the form \[ Q_1 x_1.\, \dots Q_n x_n.\, \phi(x_1, \dots, x_n\). \] where \(Q_i \in \left\{ \exists, \forall \right\}\). Quantified boolean formulas with nested quantifiers can be transformed into quantified boolean formulas with all quantifiers at the beginning.
We define \[ \mathrm{TQBF} = \left\{ \phi \text{ in QBF form} \mid \phi \right\} \] i.e. as the problem which takes in as input a QBF \(\phi\) and asks whether \(\phi\) is true.
Because TQBF implies SAT, it will be at least NP.
\[ \phi = \forall u .\, \exists v .\, (u \land v) \lor (\neg u \land \neg v) \] This is true iff when we set \(v = u\).
A similar example is \[ \psi = \exists u .\, \forall v .\, (u \land v) \lor (\neg u \land \neg v) \] Next to the previous example, it is obvious that this can never be true. So we have \(\phi \in \mathrm{TQBF}\) and \(\mathrm{\not\in \mathrm{TQBF}}\).
\[ \mathrm{TQBF} \in \mathrm{PSPACE} \]
Consider a formula \(\phi = Q_1 x_1.\, (Q' (x_2, \dots, x_n).\, \phi(x_1, \dots, x_n))\). We write this as \(Q_1 x_1 .\, \phi_1(x_1)\). We check recursively if \(\phi_1(0)\) holds and if \(\phi_1(1)\) holds. Depending on whether \(Q_1 = \forall\) or \(Q_1 = \exists\), we decide the value. \[ \phi = \begin{cases} 1 & \text{if } Q_1 = \forall \text{ and } \phi_1(0) = \phi_1(1) = 1 \\ 0 & \text{if } Q_1 = \forall \text{ and } \phi_1(0) = 0 \text{ or } \phi_1(1) = 0 \\ 1 & \text{if } Q_1 = \exists \text{ and } \phi_1(0) = 1 \text{ or } \phi_1(1) = 1 \\ 0 & \text{if } Q_1 = \exists \text{ and } \phi_1(0) = 0 \text{ and } \phi_1(1) = 0 \end{cases} \] This is an exponential time algorithm, but we can reuse the space. Let \(m\) be the length of the formula \(\phi\). In particular, we have \(n \leq m\). Let \(S(m)\) be the space needed to solve a formula of length \(m\). Then we have \[ S(\phi) = \underbrace{O(\abs{\phi})}_{\text{copy the formula}} + \underbrace{\max \left\{ S(\phi_1(1)), S(\phi_1(0)) \right\}}_{\text{decide each subformula}}. \] Then \[ S(m) = O(m) + S(m - 1) \quad\text{ and } \quad S(O(1)) = O(1). \] This means that \(S(m) = O(m^2)\).
TQBF is NPSPACE-complete. This means that it is in NPSPACE, and \[ \forall L \in \mathrm{NPSPACE} \text{ and } L \leq_p \mathrm{TQBF}. \]
\noindent Notably we've already shown it is in NPSPACE by showing it is in PSPACE. Also note that we will prove a polynomial-time reduction which is more restrictive than a PSPACE reduction. It is ok for working with PSPACE, but could potentially be too restrictive.
It suffices to show that \[ \forall L \in \mathrm{NPSPACE} .\, L \leq_p \mathrm{TQBF}. \] Consider any language \(L \in \mathrm{NPSPACE}\). Thus \(\exists\) a NTM \(M\) that decides \(L\) using space \(S(n) = O(n^d)\) for all \(d > 1\). For each input \(w \in \left\{ 0, 1 \right\}^{ * }\) we have to define a formula \(\phi(w)\) such that \[ \phi(w) = 1 \iff w \in L. \] We use configuration graphs. A node \(C\) in the graph specifies:
- what is written in the tape, taking (\(\leq S(\abs{w})\) part of the tape)
- the state of \(M\), which takes \(O(1)\) bits,
- the position of the head \(\leq \log(\abs{S(\abs{w})} \leq S(\abs{w}))\) bits.
This gives us \(2^{O(S(\abs{w}))}\) nodes. We have directed edges in the graph \(C \rightarrow C'\) iff in one step we can go from \(C\) to \(C'\). NB: If \(M\) is deterministic, we have outdegree one. Denote the configuration for the start (which depends on \(w\)) as \(C_{\text{start}}\). Also add a node \(C_{\text{accept}}\) connecting from all accepting configurations. \[ w \in L \iff \text{ in the graph } G(w) \text{ there exists a path from } C_{\text{start}} \text{ to } C_{\text{accept}}. \] There exists a propositional formula which \(\psi_0(C, C')\) which tells whether there exists a directed edge from \(C\) to \(C'\). This was done in the proof of Cooks-Levin's theorem. We want a formula \(\psi_i\) with the following property: \[ \psi_i(C, C') \iff \exists \text{a path in } G(w) \text{ from } C \text{ to } C' \text{ of length } \leq 2^i. \] We already have \(\psi_0\). We want \(\psi_i\) to be polynomial in \(i\). We define the function by induction. To use this we will need \[ \abs{\operatorname{nodes}(G(w))} \leq 2^{\text{something}}. \] Then \(2^{O(S(\abs{w}))} \leq 2^{.}\), so \(i = O(S(\abs{w}))\) suffices. For \(i \geq 1\) we get \[ \psi_i(C, C') = \exists C'' .\, \psi_{i - 1}(C, C'') \land \psi_{i - 1}(C'', C'). \] This formula works well but is not of polynomial size, such as \(\psi_i\) has length 2i - 1 because it doubles at each step.
We can instead write \[ \psi_i(C, C') = \exists C'' .\, \forall D_1 .\, D_2 .\, \left( \left( D_1 = C \land D_2 = C'' \right) \lor \left( D_1 = C'' \land D_2 = C' \right) \right) \implies \psi_{i - 1}(D_1, D_2). \] Thus \(\psi_i\) has length \(\underbrace{O(S(\abs{w}))}_{\text{size of a configuration node}} + O(\text{length of } \psi_{i - 1})\). By induction, \(\psi_i\) has length \(O(i \cdot S(\abs{w}))\). Then \[ \psi_{O(S(\abs{w}))} = O(S(\abs{w})^2). \] Note here that we represent the implication \(p \implies q\) by \(\neg p \lor q\). Also in \(\psi_{i - 1}\) there are quantifiers, so we have to normalize the formula first on each recursive call.
\noindent This trick of splitting things in half has been used multiple times.
\[ \mathrm{PSPACE} = \mathrm{NPSPACE}. \]