# Tag Info

Accepted

### What are the obstructions to extending $L=SL$ to $L=NL$?

The central problem is that, on directed graphs, even a truly random walk doesn't hit all the vertices in expected polynomial time, let alone a pseudorandom walk. The standard counterexample here is ...
Accepted

### Nondeterministic speed-up of deterministic computation

You should not expect an exciting speed-up. We have $$\mathrm{DTIME}(f(n))\subseteq\mathrm{NTIME}(f(n))\subseteq\mathrm{ATIME}(f(n))\subseteq\mathrm{DSPACE}(f(n)),$$ and the best known simulation of ...
• 17.4k
Accepted

• 14k
Accepted

### Most non-deterministic automaton

Here is a construction over a binary alphabet, which moreover yields a minimal DFA of size $2^n$. Consider the NFA over $\Sigma=\{a,b\}$ with states $[n]=\{1,\dots,n\}$ such that the starting state is ...
• 17.4k
Accepted

### NLOGTIME versus $\exists$DLOGTIME

Yes, at least if we either allow $\log n \log^{O(1)} \! \log n$ time, or $O(\log n)$ queries (input, '∃' tapes, and nondeterminism) with $\log n \log^{O(1)} \! \log n$ other computation time. A given ...
• 2,577

### Number of minimal DFAs of size at most $m$?

(NB: the upper bound given in the accepted answer is better or equal to the one given here) An upper bound is proposed in this paper given in one of the previous comments: “On the number of distinct ...
• 427
Accepted

• 823
1 vote

### How is memory being used by an algorithm, to define its space complexity?

Let’s start with your example of nondeterminism for a second. It’s not generally anything like “a record of failed attempts”. It’s the extra memory needed for the algorithm to store stuff it needs in ...
• 804

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