2
$\begingroup$

In the definition of a complexity class like P, where they reference Deterministic Turing machines (DTMs), I don't see any restriction on # of tapes these DTMs are allowed to use.

If a language L is in P do all its words have to be decidable in polynomial time by a 1-tape, 2-tape,....k-tape Turing machine in polynomial time?

$\endgroup$
1

1 Answer 1

1
$\begingroup$

Let $\mathsf{P^k}$ be the class of problems solvable in polynomial time on deterministic Turing machines with $k$ tapes. Then $$ \mathsf{P^1} = \mathsf{P^2} = \mathsf{P^3} = \mathsf{P^4} = \mathsf{P^5} = \cdots $$ Let $\mathsf{PD^{d}}$ be the class of problems solvable in polynomial time on deterministic Turing machines with access to a $d$-dimensional infinite tape. Then $$ \mathsf{P^1} = \mathsf{PD^1} = \mathsf{PD^2} = \mathsf{PD^3} = \mathsf{PD^4} = \mathsf{PD^5} = \cdots $$ Similarly, $\mathsf{P}$ is also the class of problems solvable in polynomial time on RAM machines, which have a random-access memory (i.e. you can implement indexing $A[i]$ without needing the head to scan to the $i$th position of the tape).

The definition of $\mathsf{P}$ is very robust to the particular machine model used, and this makes $\mathsf{P}$ a very natural complexity class. This is similar to the class of all decidable languages, which can be defined in countless ways. The exact way you define $\mathsf{P}$ is arbitrary, since all definitions amount to the same complexity class.

The story gets a bit more complicated when we consider computation models other than deterministic machines (of any kind). For example, are probabilistic polytime algorithms stronger than deterministic ones? The answer might depend on the error. Probabilistic polytime algorithms with constant error probability define the complexity class $\mathsf{BPP}$, which is believed (by most) to be the same as $\mathsf{P}$. If we allow unbounded error we get $\mathsf{PP}$, which contains $\mathsf{NP}$, and so such algorithms are probably more powerful than deterministic ones. Similarly, quantum algorithms with bounded errors form the complexity class $\mathsf{BQP}$, which contains problems such as factoring which are not believed (by most) to be solvable in classical polynomial time.

$\endgroup$
4
  • $\begingroup$ This is classical material, so you can likely find it in standard textbooks. $\endgroup$ Mar 28, 2020 at 19:30
  • $\begingroup$ P^1 = P^2 = P^3... do you have a reference or a proof for this? Is there any textbook that walks you through this logic? Thank you. I don't philosophically understand why you can't simulate with a DTM branching computation (NDTM) by having a tape for each branch and then continuing the computations happening on each branch in parallel on each tape? Where does the extra computational power come from when it seems to me like having many branches is the same thing as having many tapes? $\endgroup$
    – DeeDee
    Mar 28, 2020 at 19:31
  • $\begingroup$ The number of branches increases exponentially. You will have to maintain too many branches, which will take exponential time. $\endgroup$ Mar 28, 2020 at 19:33
  • $\begingroup$ For example, your program might first nondeterministically guess a 3-coloring if the input graph, then proceed to verify it. Trying all 3-colorings deterministically would take exponential time. $\endgroup$ Mar 28, 2020 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.