World's most popular travel blog for travel bloggers.

[Solved]: "P may collapse" vs. Time hierarchy theorem

, , No Comments
Problem Detail: 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, 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?

Asked By : Albert Hendriks

Answered By : Lieuwe Vinkhuijzen

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 ;)

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback