Questions tagged [time-hierarchy]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
7 votes
1 answer
175 views

Is any function between $n$ and $n\log n$ time-constructible on a 1-tape TM?

The question: Is there an $f$ in $\omega(n) \cap o(n \log n)$ that is time-constructible on a 1-tape DTM? I.e. $f$ such that $\lim_{n\to\infty} \frac{n}{f(n)} = \lim_{n\to\infty} \frac{f(n)}{n \log n} ...
Neal Young's user avatar
  • 10.3k
0 votes
0 answers
67 views

What is the meaning of the additive epsilon term in the definition of a time constructible function?

There is a well-known theorem that states that a function $f$ is time constructible if and only if $f$ can be computed in time $O(f)$. But this theorem comes with some conditions: $f$ must be a ...
user70015's user avatar
6 votes
0 answers
85 views

Time hierarchy for one-tape Turing machines

The time hierarchy for multitape Turing machines is tight (see [1]): if $f(n)=o(g(n))$ and $f,g$ are well-behaved, then $\textrm{DTIME}(f(n))\subsetneq \textrm{DTIME}(g(n))$. However, for one-tape ...
QMath's user avatar
  • 303
3 votes
0 answers
73 views

Time complexity of context-free languages

I am reading an old paper [1] about time complexity of context-free languages. The computational model is the standard one-tape Turing machine. It is written on page 377 without a proof that "we ...
QMath's user avatar
  • 303
4 votes
0 answers
383 views

Simulating a $k$ tape Turing machine with a 2 tape Turing machine

Let $k$ be an (fixed, $3$ for instance) integer, what is the fastest simulation of a $k$ tape Turing machine by a two tape Turing machine? That is we're looking for the best 2 tape TM $U$, such that ...
ULechine's user avatar
  • 149
3 votes
0 answers
114 views

Increasing Functions in Non-deterministic Time Hierarchy Theorems

I was going over the proofs of the non-deterministic time hierarchy theorem (the one in Arora-Barak and the one by Fortnow and Santhanam). They are available here: http://theory.cs.princeton.edu/...
Anon's user avatar
  • 31
10 votes
0 answers
200 views

Provable BPP Hierarchy

No Time Hierarchy theorem is known for $\mathsf{BPTIME}$, however, consider the following simple modification of the definition: A language is in $\mathsf{ProvableBPTIME}[f(n)]$ if there is a ...
domotorp's user avatar
  • 13.9k
6 votes
1 answer
339 views

Are all problems in the same time hierarchy related to each other?

In this problem, "runtimes" refer to worst-case complexity compared up to constant factor. Say you have two problems, A and B, in the same time hierarchy, and it is clear that algorithm P ...
chxu's user avatar
  • 69
3 votes
2 answers
186 views

$DTIME_1(o(n^2))\setminus$ REGULAR

Maybe this is well-known, but I couldn't find any example of a non-regular lanugage that is decidable on a single-tape Turing machine in subquadratic time. Help! Related paper: On the structure of ...
domotorp's user avatar
  • 13.9k
1 vote
1 answer
82 views

Can we replace deterministic part of alternative turing machine with some other equivalent machines?

I'm sorry if it is a low level question but I am so confusing. If $DTime(n)\subseteq \Sigma_2Time(n^{0.2})$ then $DTime(n) \subseteq \Sigma_2DTime(n^{0.2})$ Is this true that $\Sigma_2DTime(n^{0.2})...
Song Hai's user avatar
1 vote
0 answers
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)$ ...
Mohsen Ghorbani's user avatar
7 votes
2 answers
385 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 ...
exfret's user avatar
  • 643
2 votes
1 answer
180 views

How fine-grained can the time hierarchy theorem be in a reasonable model?

One version of the sharp or additive space hierarchy theorem is that for Turing machines (and a number of other deterministic sequential computational models) $\mathrm{Space}(f-ω(\log(n+f))) ⊊ \mathrm{...
Dmytro Taranovsky's user avatar
12 votes
1 answer
534 views

Time Hierarchies in DSPACE(O(s(n)))

The time hierarchy theorem states that turing machines can solve more problems if they have (enough) more time. Does it hold in some way if the space is limited asymptotically? How does $\textrm{DTISP}...
Henning's user avatar
  • 59
2 votes
0 answers
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), ...
Turbo's user avatar
  • 12.8k
8 votes
1 answer
379 views

Hierarchy theorem for NTIME intersect coNTIME?

$\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}(...
William Hoza's user avatar
  • 1,733
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), ...
GMB's user avatar
  • 2,393
12 votes
1 answer
628 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 ...
domotorp's user avatar
  • 13.9k
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-...
Jeff Burdges's user avatar
  • 1,216
5 votes
0 answers
172 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 "...
David G's user avatar
  • 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}$ ...
Sasho Nikolov's user avatar
10 votes
2 answers
668 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$ ...
Marc Bury's user avatar
  • 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 ...
Ludovic Patey's user avatar
19 votes
2 answers
910 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}...
Joseph's user avatar
  • 387
6 votes
1 answer
504 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 ...
chazisop's user avatar
  • 3,796
22 votes
1 answer
493 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 ...
András Salamon's user avatar