We have seen that, thanks to the Church-Turing thesis, all computational models as powerful as Turing machines are equivalent in terms of what problems are decidable and undecidable.

However, the efficiency of these solutions *can* vary on different computational models.

How can we decide $A = \{0^k1^k\; |\; k \ge 0\}$ with a multi-tape Turing machine in linear time $TIME(n)$?

The complexity of a problem depends on the computational model being used.

We can convert any multi-tape Turing machine into an equivalent single-tape one using the technique discussed when we covered Turing machine variants. The technique is repeated here:

Given some multi-tape Turing machine $M$, we can build an equivalent single tape machine $S$ is defined as follows:

$S =$ "On input $w = w_1w_2...w_n:$

Put the tape into the format described above:

$\#\dot{w_1}w_2...w_n\#\dot{\sqcup}\#\dot{\sqcup}\#\dot{\sqcup}\#\dot{\sqcup}...$

- To simulate a single move, $S$ scans the entire tape to see which symbols are under the tape heads (the dotted symbols). It then makes a second pass according to the transition function of $M$ to change the tape: writing new symbols under the tape heads, and moving the dots left or right.
- If at any point $S$ moves a tape head to the right onto a $\#$ symbol, it means $M$ has moved the tape head to the end of a tape. So $S$ writes a blank symbol over the $\#$ symbol, shifts the entire rest of the tape one position to the right, and restores the $\#$ symbol. It then continues on where it left off."

How much computational complexity is introduced with this simulation? If the multi-tape Turing machine $M$ runs in $t(n)$ time, how much time is required for the single-tape machine $S$ provided by this construction?

Because $S$ must scan across the tape for each step of the computation, the time required is equal to the time required to scan the tape times the number of steps $t(n)$.

It may seem it takes $\mathcal O(n)$ time to scan the tape, but the operation
of $M$ may be *increasing* the length of the tape as it runs.
The maximum amount $M$ can increase the tape is $k \times t(n)$ where $k$ is the
number of tapes.

Thus, the time to scan the tape is at most $\mathcal O(t(n))$, and the full running time of $S$ is $\mathcal O(t^2 (n))$.

Next, we'll consider a non-deterministic Turing machine. We define the running time $t(n)$ of a non-deterministic Turing machine as the maximum number of steps in any branch of the computation:

Recall that the algorithm for simulating a non-deterministic Turing machine $N$ on a deterministic Turing machine $D$. It uses a breadth first search of the tree of computation.

If we use this method to simulate $N$ which runs in time $t(n)$, how much time will the deterministic Turing machine $D$ take?

By the definition of a non-deterministic Turing machine complexity, every branch of the tree has length at most $t(n)$. Every node in the tree has at most $b$ children where $b$ is the maximum number of choices at any point in the $N$.

Thus, the total number of leaves in the tree is at most $b^{t(n)}$. The number of nodes in the tree is less than twice the number of leaves. So we can bound it by $\mathcal O(b^{t(n)})$.

The time it takes to travel from the root to any one node is $\mathcal O(t(n))$. Thus the total running time of $D$ is $O(t(n) b^{t(n)})$. This is equal to $2^{\mathcal O(t(n))}$.

The simulation actually uses a three-tape Turing machine. As discussed above, this at most squares the running time, so we have $(2^{\mathcal O(t(n))})^2 = 2^{\mathcal O(2t(n))} = 2^{\mathcal O(t(n))}$.

The difference between a single-tape and multi-tape Turing machine is much smaller than the difference between a deterministic and non-deterministic one. We will call polynomial differences in time small, and exponential differences large.

An algorithm that completes in polynomial time is usually useful, whereas an exponential one rarely is.

All reasonable deterministic models of computation are *polynomially equivalent*.
That means that one can simulate the other using only a polynomial increase in running
time.

$P$ is the class of languages that are decidable on a deterministic single-tape Turing machine in polynomial time:

$P = \bigcup\limits_{k} TIME(n^k)$

That is, $P = \{n, n^2, n^3, n^4...\}$.

$P$ is a useful class to talk about because:

- $P$ is invariant to the model of computation we discuss.
- $P$ mostly corresponds to the set of problems that have "feasible" solutions.

One example of problem in $P$ is the $PATH$ problem:

$PATH = \{\langle G, s, t\rangle\; |\; G$ is a directed graph that has a path from $s$ to $t\}$.

How can we show that $PATH$ is in $P$?

The following algorithm decides $PATH$:

$M =$ "On input $\langle G, s, t \rangle$:

- Place a mark on node $s$.
- Repeat until no nodes are marked:
- Scan all edges of $G$. If an edge $(a, b)$ is found where $a$ is marked, and $b$ is unmarked, mark node $b$.

- If $t$ is marked, accept. Otherwise reject.

What is the complexity of $M$?

$P$ also includes most problems that have efficient solutions that you have dealt with:

- Searching and sorting problems.
- Numerical algorithms such as adding, subtracting, multiplication.
- Every language that is regular or context-free $\in P$. There are algorithms to solve $A_{DFA}$ and $A_{CFG}$ in polynomial time.

We will see a few more examples of problems in $P$.

Copyright © 2019 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.