4
$\begingroup$

https://en.wikipedia.org/wiki/P_versus_NP_problem states:

If graph isomorphism is NP-complete, the polynomial time hierarchy collapses to its second level.

They further state that this may be unlikely, but at least it's a possibility. However, https://en.wikipedia.org/wiki/Time_hierarchy_theorem states:

The theorem also guarantees that there are problems in P requiring arbitrarily large exponents to solve; in other words, P does not collapse to DTIME($n^k$) for any fixed k. For example, there are problems solvable in $n^{5000}$ time but not $n^{4999}$ time.

Why don't the above two quotes contradict each other?

$\endgroup$

2 Answers 2

5
$\begingroup$

The time hierarchy theorem only says that P does not collapse to $DTIME(n^k)$, that is, it says that giving one deterministic Turing Machine more time than another deterministic Turing Machine gives it more power. There is an analogous theorem for nondeterministic Turing Machines, called the Nondeterministic Time Hierarchy Theorem, which implies that NP does not collapse to $NTIME(n^k)$ for any fixed $k$.

The P vs NP question, however, it about how deterministic Turing Machines relate to nondeterministic Turing Machines. Just for clarity, the sets are defined as follows:

$$P = DTIME(poly)= \bigcup_{k\in \mathbb{N}} DTIME(n^k) \\ NP = NTIME(poly) = \bigcup_{k\in \mathbb{N}} NTIME(n^k)$$

For example, if P=NP, then we may find out that for all $k:\ NTIME(n^k)\subseteq DTIME(n^{7k})$. (Note that even if this is true, P still does not collapse to $DTIME(n^k)$ for any fixed $k$.) The polynomial hierarchy, which you refer to, informally, is a way to obtain more classes from P and NP by going "up" to more difficult problems in much the same way that we went from P to NP. Asking whether it collapses to its second level is the same as asking the P vs NP question, but for the higher level. For example, asking whether the polynomial hierarchy collapses to its second level is to ask how $ATIME(poly, 2)$ relates to $ATIME(poly, 3)$, with $ATIME(t(n), a(n))$ the set of languages decidable by an alternating Turing Machine in $t(n)$ time and using $a(n)$ alternations, with $P=ATIME(poly, 0)$ and $NP=ATIME(poly, 1)$, where the Alternating Turing Machine is something interesting enough to read up on this Sunday afternoon ;)

$\endgroup$
1
6
$\begingroup$

The polynomial hierarchy is not $\mathsf{DTIME}(n^k)$ for various $k$, but rather a polynomial time version of the arithmetical hierarchy.

$\endgroup$

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.