Notes - Computational Complexity HT25, Nondeterminism

• Accept: There exists at least one accepting path
• Reject: All paths end with a reject state

For all $x \in \Sigma^\ast$, all paths of $M$ either accept or reject in time $t$.

For all $x \in \Sigma^\ast$, all paths of $M$ either accept or reject in space $s$.

To accept as a non-deterministic Turing machine means that there is at least one accepting path, and rejecting means that all paths end with a reject state. So flipping the output of one particular path does not tell you about the global properties.

Suppose that some language $L$ satisfies the above condition where $M$ is a polynomial time decider for $R$. We wish to show it’s accepted by some polynomial time NTM $N$. Define as follows:

• $N$ on input $x$:
  • Computes $p( \vert x \vert )$, guessing $y$ of length $\le p( \vert x \vert )$.
  • Runs $M(x, y)$ and accepts iff $M$ accepts.

For the other direction, suppose that $N$ is a NTM running in time $q( \vert x \vert )$ and deciding a language $L$. Let $R(x, y) = 1$ iff $y = \langle c _ 1, c _ 2, \ldots, c _ t \rangle$ encodes an accepting computation of $M$ on $x$.

Note that each configuration $c _ i$ of $M$ has size $O(q( \vert x \vert ))$, and there are a maximum of $t \le q( \vert x \vert )$ configurations, so the total size of $y$ is bounded by $q^2$, a polynomial.

\[\mathsf{NP} = \bigcup_{k \in \mathbb N} \mathsf{NTIME}(n^k)\]

$\mathsf{NP}$ is the set of all languages $L$ such that there exists a polynomial time relation $R$ such that $\forall x$, $x \in L$ iff $\exists y$ such that $ \vert y \vert = \text{poly}( \vert x \vert )$ and $R(x, y) = 1$.

\[\mathsf{NEXP} = \bigcup_{k \in \mathbb N} \mathsf{NTIME}(2^{n^k})\]

\[\mathsf{coNP} = \\{ L \mid \overline L \in \mathsf{NP}\\}\]

$L \in \mathsf{coNP}$ iff there is a polynomial-time computable relation $R$ such that $x \in L$ iff $\forall y \in \{0, 1\}^{\text{poly}( \vert x \vert )} . R(x, y)$.

Suppose $L \in \mathsf{coNP}$. Then $\overline L \in \mathsf{NP}$. Therefore there is a polynomial time relation $\overline R$ such that $x \in \overline L$ iff $\exists y \in \{0, 1\}^{\text{poly}( \vert x \vert )} y . \overline R(x, y)$. Thus $x \in L$ iff $\forall y \in \{0, 1\}^{\text{poly}( \vert x \vert )} . \lnot \overline R$, which gives the required characterisation by taking $R := \lnot \overline R$.

Now suppose that $L$ is characterised by $x \in L$ iff $\forall y \in \{0, 1\}^{\text{poly}( \vert x \vert )} . R(x, y)$. Then $x \in \overline L$ iff $\exists y \in \{0, 1\}^{\text{poly}( \vert x \vert )} y . \lnot R(x, y)$, and so $\overline L$ is in $\mathsf{NP}$. Hence $L \in \mathsf{coNP}$.

\[\mathsf{NTIME}(T) \subseteq \mathsf{DSPACE}(T)\]

Overall idea: Enumerate all possible sequences of configurations of the non-deterministic machine, and check if they are valid. This might take a very long time but only uses $O(T)$ space.

---

Suppose $L \in \mathsf{NTIME}(T)$ with corresponding TM $M$.

Define a deterministic TM $N$ which runs in space $O(T)$ as follows. Let $d$ be a constant that bounds the number of successors of any configuration of $M$.

On input $x$:

• $N$ uses the space constructibility of $T$ to compute $T( \vert x \vert )$.
• $N$ enumerates all strings of length $T( \vert x \vert )$ over the alphabet $\{1, 2, \ldots, d\}$ which represent possible computation paths of $M$.
• For each possible computation path, $N$ checks if the computation path is valid and leads to acceptance, halting and accepting if it does.
• If none of the computation paths is a valid accepting path, $N$ rejects.

Note that $N$ only uses space $O(T( \vert x \vert ))$ since at any point in its computation, it only needs to store the current computation path of $M$ being simulated, as well as the current configuration of $M$.

Since the computation path being simulates is of length $O(T( \vert x \vert ))$, $M$ uses space at most $O(T( \vert x \vert ))$, and hence the stored configuration of $M$ also has size at most $O(T( \vert x \vert ))$.

\[\mathsf{NSPACE}(S) \subseteq \mathsf{DTIME}(2^{O(S)})\]

Let $L$ be any language in $\mathsf{NSPACE}(S)$ and $M$ a Turing machine that decides $L$ in space $O(S)$.

Note that there are at most $(n+1)2^{O(S)}$ possible configurations of $M$ on any input of length $n$, since there are at most $(n+1)$ possible positions of the input tape head, at most $\text{poly}(S)$ positions of the work tape heads, at most $2^{O(S)}$ possible contents of the work tapes, and at most constantly many possible states of the machine.

Treat these configurations as a graph with edges between configurations. Implement BFS on the configuration graph, which takes space $2^{O(S)}$ by constructing the adjacency matrix.

For all $L’ \in \mathsf{NP}$, $L’ \le _ m^\text{poly} L$.

Suppose $L$ is $\mathsf{NP}$-complete. Then $\mathsf{P} \ne \mathsf{NP}$ iff $L \notin \mathsf{P}$. (i.e. to prove that $\mathsf{P} \ne \mathsf{ NP }$, it suffices to show that any $\mathsf{ NP}$-complete language is not in $\mathsf{P}$).

---

Proof: The forward direction follows from the fact that if $L \in \mathsf{ P}$, then all $\mathsf{NP}$-languages could be decided in polynomial time, and the backwards direction follows from the fact that $L \in \mathsf{NP}$.

\[L = \\{ \langle M, x, 1^t \rangle : M \text{ is an NTM that accepts }x\text{ in }t \text{ steps} \\}\]

---

Proof: To establish that $L$ is $\mathsf{NP}$, run the universal NTM for $t$ steps with input $\langle M, x \rangle$ and accept only if $M$ accepts $x$. This does polynomial time.

Now suppose $L’ \in \mathsf{NP}$ and $M _ {L’}$ is an NTM deciding $L$ in time $p( \vert x \vert )$ for large enough $x$. Define

\[f(x) = \langle M_{L'}, x, 1^{p(|x|)} \rangle\]

Note that $M _ L$ is a fixed machine that does not depend on the input, and hence $f(x)$ can be computed in polynomial time. Then $x \in L \iff M _ L$ accepts $x$ within $p( \vert x \vert )$ steps, as required.

@todo

@todo

@todo

Let $A$ be a polynomial time algorithm for $\mathsf{SAT}$. We define a recursive algorithm $S$ which solves the search problem in polynomial time.

Given a formula $\varphi$, if $\varphi$ has no variables, $S$ evaluates $\varphi$ in polynomial time and outputs the empty string if $\varphi$ is true and “fail” otherwise.

If $\varphi$ does contain variables, let $x$ be the lexicographically first variable in $\varphi$. Let $\varphi _ 0$ be the formula obtained from $\varphi$ by substituting $x = 0$, and $\varphi _ 1$ be obtained by substituting $x = 1$. $S$ runs $A$ on $\varphi _ 0$ and if accepts, $S$ outputs $x = 0$ concatenated with $S(\varphi _ 0)$, otherwise $S$ outputs $x = 1$ concatenated with $S(\varphi _ 1)$.

This takes polynomial time, since there are polynomially many variables and each iteration takes polynomial time.

$L \in \mathsf{coNP}$ and for every language $L’ \in \mathsf{coNP}$, $L’ \le _ m^\text{poly} L$.

$L$ is $\mathsf{coNP}$-complete with respect to polynomial time $m$-reductions iff $\overline L$ is $\mathsf{NP}$-complete with respect to polynomial time $m$-reductions.

\[\mathsf{TAUT} = \{ \varphi \mid \varphi \text{ is a propositional tautology}\}\]

It is $\mathsf{coNP}$-complete as $\varphi$ is a tautology iff $\lnot \varphi$ is unsatisfiable, so $\mathsf{TAUT}$ and $\mathsf{UNSAT}$ polynomial-time $m$-reduce to one another. As $\mathsf{UNSAT}$ is $\mathsf{coNP}$-complete (it is the complement of a $\mathsf{NP}$-complete language), it follows that $\mathsf{TAUT}$ is $\mathsf{coNP}$-complete.

Any language $L \in \mathsf{NP}$ is decidable in polynomial time with oracle access to $\overline L \in \mathsf{coNP}$.