Notes - Computational Complexity HT25, Non-determinism



Flashcards

Basic definitions

When does a non-deterministic Turing machine accept an input, and when does it reject?


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

@Define what it means for an NTM $M$ to run for time $t$.


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

@Define what it means for an NTM $M$ to run in space $s$.


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

Why is it not simply the case that

\[\mathsf{NTIME}(t) = \overline{\mathsf{NTIME}(t)}\]

by simply flipping the status of the deciding non-deterministic Turing machine?


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.

@Define $\mathsf{NP}$ in terms of polynomially sized witnesses.


$\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$.

@Prove that it’s accurate to characterise $\mathsf{NP}$ as 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$.


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.

@Prove that the directed graph reachability problem which asks if there is a path from vertex $s$ to vertex $t$ in a directed graph $G$ is in $\mathsf{NLOGSPACE}$.


Guess a sequence of vertices

\[v_0 = s, v_1, \ldots, v_k\]

where $k \le n$. At stage $i$, maintain only $i$ in memory with vertices $v _ {i-1}$ and $v _ i$.

Check that $i \le n$ and that there is an edge from $v _ {i-1}$ to $v _ i$.

If either of the conditions fail, reject. Otherwise, check whether $v _ i = t$ and accept if so, or increment $i$.

Simulation arguments

Simulating deterministic time with non-deterministic time

Suppose $T : \mathbb N \to \mathbb N$ is a space-constructible time bound. @State a relationship between $\mathsf{NTIME}(T)$ and $\mathsf{DSPACE}(T)$.


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

@State and @justify a proposition which relates $\mathsf{NP}$-completeness of a language and the $\mathsf{P} \stackrel?= \mathsf{NP}$ question.


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}$.

@Define the bounded NTM acceptance problem, and @prove that it’s $\mathsf{NP}$-complete.


\[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.

$\mathsf{NP}$-complete problems

@Prove that $\mathsf{SAT}$ is $\mathsf{NP}$-complete.


@todo

@Prove that $3\text{-}\mathsf{SAT}$ is $\mathsf{NP}$-complete.


@todo

@Prove that $\mathsf{CLIQUE}$ is $\mathsf{NP}$-complete.


@todo

Search to decision reductions

@Prove that if $\mathsf P = \mathsf{NP}$, then there is a polynomial time algorithm which given a formula $\varphi$ outputs a satisfying assignment if $\varphi$ is satisfiable.


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.




Related posts