Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [time-hierarchy]

The tag has no usage guidance.

26 questions
Filter by
Sorted by
Tagged with
243 views

• 23
1 vote
138 views

### Is a limited space-time hierarchy theorem correct? [duplicate]

Is a limited (deterministic) space-time hierarchy theorem correct? For example, we have a limitation of $O(n^2)$ space then: can we find problems that can be solved in $O(n^k)$ time and $O(n^2)$ ...
393 views

### Are space and time hierarchies even comparable?

I am wondering if there are any results to what extent the space and time hierarchies "disagree" on which problem is harder. For example, is it known whether there are languages $L_1$ and $L_2$ such ...
• 653
181 views

• 59
106 views

### On analogies between parallel complexity and polynomial time hierarchy structure?

Is it known $\mathsf{RNC=NC\iff P=RP}$ or $\mathsf{BPNC=NC\iff P=BPP}$? Are there any analogies (such as collapse results, problems which suggest analogies such as gcd(in NC) and factoring (in P), ...
• 12.9k
380 views

$\newcommand{\cc}[1]{\mathsf{#1}}$Does a theorem along the following lines hold: If $g(n)$ is a little bigger than $f(n)$, then $\cc{NTIME}(g) \cap \cc{coNTIME}(g) \neq \cc{NTIME}(f) \cap \cc{coNTIME}(... • 1,743 2 votes 1 answer 167 views ### Is there an additive time hierarchy theorem? I would like something like this to be true: Conjecture: There is a function$g(n)$such that for all functions$f(n)$(perhaps satisfying some reasonable properties, like time-constructability), ... • 2,403 12 votes 1 answer 632 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 ... • 14k 3 votes 0 answers 206 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 linear-... • 1,216 5 votes 0 answers 177 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 "... • 532 31 votes 2 answers 1k 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}$... • 18.2k 10 votes 2 answers 670 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$... • 1,338 31 votes 3 answers 2k 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 ... • 1,763 19 votes 2 answers 918 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$O(n^{k-1}...
• 387
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 ...