Skip to main content

# Tag Info

## Hot answers tagged time-hierarchy

10 votes
Accepted

### Are space and time hierarchies even comparable?

You can get the situation you describe by choosing weird functions $f(n)$ and $g(n)$. For example, let $g(n) = n^3$ and f(n) = \begin{cases} n & \text{if $n$ is odd}, \\\ 2^{n^5} & \text{...
• 2,768
9 votes
Accepted

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

For example, I think you can decide if $\lfloor\log_2|w|\rfloor$ is even in time $O(n\log n)$: you first overwrite the input string with all 1s, and then do $\log n$ passes over the string where you ...
• 17.9k
7 votes

### Justification of log f in DTIME hierarchy theorem

For a fixed number of tapes greater than one, $\mathrm{Time}(o(f)) ⊊ \mathrm{Time}(O(f)$) for time-constructible $f$. The logarithmic overhead comes from the tape reduction theorem, where any number ...
• 2,577
6 votes
Accepted

1 vote
Accepted

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

The three ingredients of a diagonalization based proof of the time hierarchy theorem are universal simulation, timing, and reversal. By choosing (or defining) a computational model where these ...
• 2,577

Only top scored, non community-wiki answers of a minimum length are eligible