30
votes
Accepted
Who introduced nondeterministic computation?
I have always seen the notion of nondeterminism in computation attributed to Michael Rabin and Dana Scott. They defined nondeterministic finite automata in their famous paper Finite Automata and Their ...
- 18.1k
22
votes
Accepted
How is the MA version of SETH proven to be false?
You can find a preprint by following this link http://eccc.hpi-web.de/report/2016/002/
EDIT (1/24) By request, here is a quick summary, taken from the paper itself, but glossing over many things. ...
- 26.7k
19
votes
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 ...
- 306
11
votes
Who introduced nondeterministic computation?
Here is what Odifreddi says on the issue:
"Our model of a Turing machine is deterministic,
in the sense that the instructions are required to be consistent
(at most one of them is applicable ...
- 21.4k
11
votes
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 ...
- 15.6k
10
votes
Is a quadratic nondeterminism speed-up of deterministic computation plausible?
Note that even a result along the lines of $\mathsf{DTime}(\tilde{O}(n^2)) \subseteq \mathsf{NTime}(n^{2-\epsilon})$ would violate NSETH as univariate polynomial identity testing (as defined in ...
- 2,295
8
votes
Accepted
Number of minimal DFAs of size at most $m$?
According to Ishigami Y., Tani S. (1993) The VC-dimension of finite automata with $n$ states,
http://link.springer.com/chapter/10.1007/3-540-57370-4_58
,
the VC-dimension of the concept class of $n$-...
- 10.2k
8
votes
Does there exist a hardest DCFL?
The paper
J.-M. Autebert, Une note sur le cylindre des langages déterministes,
Theoretical Computer Science 8 (1979), 395-399
gives a short proof of the following result (credited to Greibach) ...
- 4,761
8
votes
Does there exist a hardest DCFL?
There actually is a hardest DCFL, which is a deterministic version of Greibach's; it was introduced by Sudborough in 78 in On
deterministic
context-free
languages,
multihead
automata,
and
the
...
- 3,916
8
votes
Does there exist a hardest DCFL?
An identical homomorphism characterization of DCFL does not seem to be possible. The following is extracted from Greibach's original paper.
We show that every context-free language can be expressed ...
8
votes
Accepted
Nondeterminism is on average useless for circuits?
1) Realize that nondeterminism is a red herring here. You could have used alternation or circuits that have gates that solve the halting problem. It boils down to a simple counting argument that once ...
- 8,556
7
votes
Is the Triangle Finding decision problem in $coNTIME(\tilde{O}(n^2))$?
Update: Sadly, it seems that my initial idea (see below) was incorrect, but it led to some fruitful discussion in the comments. As a result, the question is still open.
Please let me know if you have ...
- 5,045
7
votes
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 ...
- 11.3k
7
votes
Accepted
Determinism and pi-calculus
There are plenty such typing systems.
Most work is based on the linear/affine typing system introduced
in (1) and generalised in (2). Here are the main works on this subject.
In (3) the typing system ...
- 10.6k
7
votes
Who introduced nondeterministic computation?
Rabin and Scott introduced the nondeterministic finite automata with their research paper published in IBM journal, April 1959. In the paper they mentioned:
we have adopted an even simpler form of ...
- 79
6
votes
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.4k
6
votes
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,045
6
votes
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,473
6
votes
Accepted
Is $L \subset 1NL$ when $L \neq NL$?
Define the language $BACKPOINTER$ to have words of length $n+t\log n$, divided to $1+t$ parts, one of length $n$ and the rest of length $\log n$, by commas such that $BACKPOINTER=\{(x,p_1,\ldots,p_t)\...
- 13.9k
5
votes
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 ...
- 15.6k
5
votes
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,422
5
votes
Is there a non-deterministic linear time algorithm for CNF-SAT?
This is only an extended comment.
A few times ago I asked (myself :-) how fast a multitape NTM that accepts a (reasonably encoded) NP-complete language can be. I came up with this idea:
3-SAT ...
- 22.5k
4
votes
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
4
votes
Accepted
Size bound on Büchi automaton for complement
Once you have the bound $2^{2n^2}$ on the number of classes, you can note that each state in the complement automaton corresponds to an $\omega$-regular language of the form $L_{f}L_{g}^\omega$, with $...
- 5,511
4
votes
Accepted
Example demonstrating the power of non-deterministic circuits
If this problem has no progress, I have an answer.
--
I also have considered this problem since my COCOON'15 paper (before your question).
Now, I have a proof strategy, and it immediately gives the ...
- 689
3
votes
Accepted
What do stronger circuit lower bounds give in terms of derandomization?
It is known that if $E = DTIME(2^{O(n)})$ is not contained in $SIZE(2^{\varepsilon \cdot n})$ for some $\varepsilon>0$ then $BPP = P$ (https://dl.acm.org/citation.cfm?id=258590).
(Actually, a ...
- 5,290
2
votes
Is a quadratic nondeterminism speed-up of deterministic computation plausible?
Consider computing the gcd from the primitive operations of addition, subtraction, division, and remainder. The best known deterministic algorithm is the Euclidean algorithm, which takes logarithmic ...
- 693
2
votes
Is there a non-deterministic linear time algorithm for CNF-SAT?
Not exactly what your looking for, but for 1-tape NTM, the answer seems to be negative: SAT is not solvable by a 1-tape NTM in non-deterministic linear time.
According to this paper (Theorem 4.1), ...
- 560
Only top scored, non community-wiki answers of a minimum length are eligible