Notes - Models of Computation MT23, Complexity


Flashcards

Define the running time $f$ of a deterministic, total Turing machine $M$.


A function $f : \mathbb N \to \mathbb N$ where $f(n)$ is the maximum number of steps that $M$ takes before accepting or rejecting any input of length $n$.

State the speed up theorem for a language $L$ and $k$-tape Turing machine $M _ 1$.


Suppose:

  • $L$ language recognised by a $k$-tape Turing machine $M _ 1$
  • $f$ running time of $M _ 1$
  • $f(n)/n \to \infty$ as $n \to \infty$

Then:

  • For any $c > 0$, $L$ can be recognised with a $k$-tape Turing machine $M _ 2$ with running time bounded above by $c \times f(n)$.

(note the fact that it suffices for $M _ 1$ to recognise $L$ here rather than decide it).

What’s the basic idea behind the proof of the speed up theorem, i.e. that if

  • $L$ language recognised by $M _ 1$
  • $f$ running time of $M _ 1$
  • $f(n)/n \to \infty$ as $n \to \infty$

then:

  • $L$ is recognised by a new $k$-tape Turing machine $M _ 2$
  • Running time of $M _ 2$ is $c \times f(n)$ for any $c > 0$

Group collections of $m$ symbols and on the tape into one new symbol, and just have a lot more transitions.

Suppose $t : \mathbb N \to \mathbb R _ {>0}$ is a function. Define the time complexity class

\[\text{TIME}(t(n))\]

The set of languages decidable by a Turing machine with running time

\[O(t(n))\]

Suppose we have a $k$-tape Turing machine $M$ that solves a problem with running time $t(n)$. Clearly a single-tape Turing machine will be at least a bit slower slower. Can you state a theorem that bounds how much slower a single-tape Turing machine can be in the worst case? We require one extra condition.


Suppose:

  • $t : \mathbb N \to \mathbb R _ {>0}$
  • $t(n)$ running time of $k$-tape Turing machine
  • $t(n) \ge n$ for all $n$

Then:

  • There exists an equivalent single-tape Turing machine with running time $O(t^2(n))$.

Suppose you had a 3-tape Turing machine $M$, how can you build a single-tape Turing machine $N$ that simulates $M$?


Let $\Sigma _ N = \Sigma _ M$ and use the extended tape alphabet

\[\Gamma_N = \Sigma_M \cup \\{\vdash\\} \cup (\Gamma_M \cup \widehat{F_M})^3\]

where $\widehat{F _ M} = \{\hat a \mid a \in \Gamma _ M\}$ .

Suppose:

  • We have a $k$-tape TM $M$ with running time $t(n)$, alphabet $\Sigma _ M$ and tape alphabet $\Sigma _ M$
  • We want to simulate this with a 1-tape TM $N$

What is the construction used to do this, and given one extra condition, can you derive a bound on the running time of $N$?


Let $\Sigma _ N = \Sigma _ M$ and use the extended tape alphabet

\[\Gamma_N = \Sigma_M \cup \\{\vdash\\} \cup (\Gamma_M \cup \widehat{F_M})^k\]

where $\widehat{F _ M} = \{\hat a \mid a \in \Gamma _ M\}$ .

This divides the tape into $k$ tracks. Each track will contain the contents of one of $M$’s tapes, and has only one marked symbol $\hat a$, indicating the position of the corresponding tape head.

Then, on input $w$, $N$:

  1. Replaces the input with the input on the top track and fills the other two tracks with blanks, time $O(n)$
  2. For each simulated step of $M$:
    1. Scan from left end of the tape to find all three marked symbols remembering the marked symbols in the finite control (not the positions, just the symbols), time $O(t(n))$
    2. Go back to all three marks, rewriting the symbols on each track and moving the marks appropriately, time $O(t(n))$
    3. Return to the left end of the tape, time $O(t(n))$

Why is it possible to bound each of the steps in 2 by $O(t(n))$? This is because the string on each tape of $M$ has length at most $t(n)$.

Thus we do $O(t(n))$ work $t(n)$ times, so this construction gives a TM that has running time $O(t(n)^2)$. (We do need to add the extra condition that $t(n) \ge n$ for all $n$, otherwise the initial step might take longer that $O(t^2(n))$).

What does it mean for two models of computation to be polynomially equivalent?


They can simulate each other with only a polynomial increase in running time.

Define the complexity class $\text P$, once in words and then once formally.


The set of all languages decidable in polynomial time on a deterministic single-tape Turing machine.

\[\text P = \bigcup_{k \ge 0} \text{TIME}(n^k)\]

Define the running time $f$ of a non-deterministic, total Turing machine $M$.


A function $f : \mathbb N \to \mathbb N$ where $f(n)$ is the maximum number of steps that $M$ uses in any branch of its computation before accepting or rejecting any input of length $n$.

Suppose a non-deterministic single-tape Turing machine $M$ has $O(t(n))$ running time. What’s an upper bound on the time-complexity of an equivalent deterministic single-tape Turing machine, and what construction is used to show this?


\[O\left(2^{t(n)}\right)\]

Roughly, we use a three-tape Turing machine which does a breadth-first search of computation graph. Then use the fact that converting to a single-tape Turing machine at most squares the run time, which is still $O\left(2^{t(n)}\right)$.

  • Every branch in the computation tree has length bounded by $t(n)$.
  • If $b$ is the maximum number of choices for any configuration given by $N$’s transition function, then there are at most $b^{t(n)}$ leaves.
  • The total number of nodes in the tree is bounded by $O(b^{t(n)})$.
  • Visiting any node from the root is $O(t(n))$, so the running time of $D$ is $O(t(n) \cdot b^{t(n)}) = 2^{O(t(n))}$ .
  • To keep track of branches this way, we need a multi-tape Turing machine.
  • Converting from a multi-tape to a single-tape Turing machine at most squares the runtime, so overall we have $(2^{O(t(n))})^2 = 2^{O(t(n))}$.

Define the complexity class $\text{NP}$, once in words and then once formally.


The set of all languages decidable in polynomial time on a non-deterministic single-tape Turing machine.

\[\text P = \bigcup_{k \ge 0} \text{NTIME}(n^k)\]

Define a verifier $V$ for a language $A$, and define a certificate.


$V$ is a Turing machine such that

\[A = \\{w \mid V \text{ accepts } \langle w, c \rangle \text{ for some string } c\\}\]

Here $c$ is the certificate.

Quickly prove that $\text{NP}$ is the same as the class of all languages that have a polynomial time verifier, where a verifier for a language $A$ is a Turing machine $V$ such that

\[A = \\{w \mid V \text{ accepts } \langle w, c \rangle \text{ for some string } c\\}\]

  • Polynomial time verifiable implies $\text{NP}$: Assume we have a $O(n^k)$ verifier $V$. Non-deterministically guess certificates of length $n^k$ ($\star$) and run $V$ on $\langle w, c \rangle$.
  • $\text{NP}$ implies polynomial time verifiable: Assume we have a NDTM $N$ that decides $A$. Given a pair $\langle w, c \rangle$, run $N$ on $w$, using $c$ to determine nondeterministic choices made.

($\star$: The notes don’t really justify why it only suffices to check certificates of length $n^k$, but I think it is okay – any verifier that runs in polynomial time in $w$ must only use a portion of the certificate of polynomial length in $w$ (otherwise it wouldn’t be a polynomial time verifier). So if there is a verifier that uses certificates of exponential length (or really anything superpolynomial), you could find another verifier that runs on the “reduced” versions of the certificates for the original verifier, all of which will be of polynomial length. So I think you can strengthen “Assume an $O(n^k)$ time verifier $V$” to “Assume an $O(n^k)$ time verifier $V$ whose certificates are all $O(n^k)$ in length”).

Suppose $A \le _ p B$ denotes the fact that $A$ is polynomial time reducible to $B$. What does it mean for a problem $B$ to be $\text{NP}$-hard and $\text{NP}$-complete?


  • $\text{NP-hard}$: For all $A \in \text{NP}$, it holds that $A \le _ p B$.
  • $\text{NP-complete}$: $B \in \text{NP}$ and $B$ is $\text{NP}$-hard.

Which is it:

  1. $\text{NP-hard} \subseteq \text{NP-complete}$, or
  2. $\text{NP-complete} \subseteq \text{NP-hard}$

?


2, $\text{NP-complete}$ problems are both $\text{NP-hard}$ and $\text{NP}$.




Related posts