# 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.9k
Accepted

### Determining if a word of specific length exists that is not accepted by a NFA

Your problem is NP-hard, by reduction from 3SAT. Let $\varphi$ be a 3SAT formula with $m$ clauses and on the $n$ variables $x_1,\dots,x_n$. Construct a NFA over the alphabet $\Sigma=\{0,1\}$ as ...
• 12.2k
Accepted

• 14k

### Nondeterministic speed-up of deterministic computation

Here is an explanation for why a general quartic nondeterministic speed-up of deterministic computation even if true would be hard to prove: Assume that a general quartic nondeterministic speed-up of ...
• 21.7k

### Nondeterministic speed-up of deterministic computation

There are two distinct concepts: (1) Efficient simulation of deterministic machines by non-deterministic machines. (2) Speed-up results that are obtained by applying a simulation over and over again....
• 5,127
Accepted

### NFA to DFA Powerset Construction : A Partial determinization algorithm with trade-off between running time and size for the resulting automata?

The paper [HP06] is in the spirit of your idea, although in a different direction, in the context of infinite words. It can be adapted more easily to finite words. In the powerset construction, we ...
• 8,903
Accepted

### Nondeterministic Turing Machines as deciders, versus NP and co-NP

As requested, I write up my comment as an answer, hoping that I correctly understood the misunderstanding :-) Li-yao Xia's answer already clarifies that, in the context of complexity, there are only ...
• 5,493
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
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.9k

### 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

• 851
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