The time-hierarchy tag has no wiki summary.
10
votes
1answer
222 views
Is $\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$?
Define $\mathsf{DTIME}(f(n))$ as the class of languages that can be accepted by a (multitape) Turing machine in time $f(n) + 1$. (The "$+ 1$" is just to simplify notation and avoid confusion.) Notice ...
2
votes
0answers
129 views
Open questions about linear-time
What are some interesting open or solved-but-hard questions around problems having linear-time solutions? Ala riffle shuffles.
I'm especially curious about problems which people believe to be ...
4
votes
0answers
59 views
Real-time countable vs fully time-constructible
Real-time countable functions were used in time hierarchy theorem in the papers of Hartmanis and Stearns (Theorem 9, 9.1 ...) and also of Hennie and Stearns (Theorems 3, 5, 7 ...). Now it is a ...
26
votes
2answers
751 views
Hierarchy for BPP vs derandomization
In one sentence: would the existence of a hierarchy for $\mathsf{BPTIME}$ imply any derandomization results?
A related but vaguer question is: does the existence of a hierarchy for $\mathsf{BPTIME}$ ...
9
votes
2answers
385 views
What happens if we improve the time hierarchy theorems?
In a nutshell, the time hierarchy theorems say that a Turing machine can solve more problems if it has more time for computation. In detail for deterministic TM and time-constructable functions $f,g$ ...
22
votes
2answers
501 views
Justification of log f in DTIME hierarchy theorem
If we look at DTIME hierarchy theorem, we've got a log due to the overhead in simulation of a deterministic Turing Machine by a universal machine :
$DTIME(\frac{f}{\log f}) \subsetneq DTIME(f)$
We ...
14
votes
2answers
495 views
Is there a Time Hierarchy theorem for PH?
Is it true that there are problems in the polynomial hierarchy solvable in time $O(n^k)$ (by an alternating Turing machine in some level of the polynomial hierarchy) that are not solvable in ...
5
votes
1answer
303 views
Lower bounds and class separation
Consider the language $A=\{0^{k}1^{k}|k\geq0\}$ . On Sipser's book "Introduction to the Theory of Computation" an algorithm with running time $O(n\log n)$ is given, on single-tape TM. We also know ...
16
votes
1answer
254 views
Are there natural separations in the nondeterministic time hierarchy?
The original Nondeterministic Time Hierarchy Theorem is due to Cook (the link is to S. Cook, A hierarchy for nondeterministic time complexity, JCSS 7 343–353, 1973). The theorem states that for any ...
