Questions tagged [time-hierarchy]
The time-hierarchy tag has no usage guidance.
26
questions
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} ...
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 ...
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 ...
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 ...
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 ...
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/...
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 ...
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 ...
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 ...
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})...
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)$ ...
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 ...
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{...
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}...
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), ...
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}(...
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), ...
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 ...
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-...
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 "...
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}$ ...
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$ ...
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 ...
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}...
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 ...
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 ...