principleMinor
"P may collapse" vs. Time hierarchy theorem
Viewed 0 times
mayhierarchytimetheoremcollapse
Problem
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?
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?
Solution
The polynomial hierarchy is not $\mathsf{DTIME}(n^k)$ for various $k$, but rather a polynomial time version of the arithmetical hierarchy.
Context
StackExchange Computer Science Q#66565, answer score: 6
Revisions (0)
No revisions yet.