4 events
when toggle format what by license comment
Feb 15 '11 at 23:06 comment added Ryan Williams Your stronger question will be hard to resolve affirmatively; it would imply $LOGSPACE \neq NP$. Suppose there is a $c$ and a language $L$ in $\Sigma_c TIME[n^k]$ that is not in $\Sigma_d TIME[n^{k-1}]$ for every $d$. Then $LOGSPACE \neq NP$. This is because every language $L \in LOGSPACE$ is in $\Sigma_d TIME[n^2]$ for some $d$ depending on $L$ (by a Savitch-theorem-type argument). So if $LOGSPACE = NP$ then in fact every language in $\Sigma_c TIME[n^k]$ is in $\Sigma_d TIME[n^2]$ for some $d$, contradictory to what you want to show.
Feb 15 '11 at 16:36 comment added Joseph This answer very clearly demonstrates the existence of a time hierarchy theorem for every distinct level of the hierarchy. This does not immediately indicate the presence of such a theorem for PH as a whole.
Feb 13 '11 at 18:30 history edited Kaveh CC BY-SA 2.5
added links
Feb 13 '11 at 16:28 history answered Ryan Williams CC BY-SA 2.5