# Tag Info

31

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 Decision Problems, 1959. Rabin's Turing Award citation also suggests that Rabin and Scott introduced nondeterministic machines.

24

Simple answer: If there does exist a more efficient algorithm that runs in $O(n^{\delta})$ time for some $\delta < 2$, then the strong exponential time hypothesis would be refuted. We will prove a stronger theorem and then the simple answer will follow. Theorem: If we can solve the intersection non-emptiness problem for two DFA's in $O(n^{\delta})$ time,...

22

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. Suppose Merlin can prove to Arthur that for a $k$-variable arithmetic circuit $C$, its value on all points in $\{0,1\}^k$ is a certain table of $2^k$ field ...

19

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 a directed graph with $n$ vertices ordered from left to right, where each vertex has an edge leading to the vertex to its right (except for the rightmost vertex,...

14

No. It is possible that L=P and that P != NP which implies that NL != NP since NL is contained in P.

11

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 in any given situation). Randomizing elements in computing devices were introduced early on by Shannon  and De Leeuw, Moore, Shannon and Shapiro [...

11

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 deterministic time by space is still the Hopcroft–Paul–Valiant theorem $$\mathrm{DTIME}(f(n))\subseteq\mathrm{DSPACE}(f(n)/\log f(n)).$$ Thus, nondeterminism ...

10

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 section 3.2) can be solved in $\tilde{O}(n^2)$ time deterministically, but there doesn't seem to be an obvious way to use nondeterminism to help prove identity.

8

If your FSM is a DFA, then this is the Minimum Consistent DFA Problem, which is well known in the machine learning community. This problem is NP complete Gold1978 - Complexity of Automaton Identification from Given Data. The problem is also known to be hard to approximate within any polynomial factor. Indeed it is even hard to find an NFA whose number of ...

8

First, (as has now been edited into the question statement) a positive answer to your question would immediately improve the state of the art in worst-case bounds for graph isomorphism. For a $O(\sqrt{n})-\mathsf{PTIME}$ algorithm yields a $2^{O(\sqrt{n})}$-time deterministic algorithm, but the current best known for GI is only $2^{O(\sqrt{n \log n})}$ ...

8

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) which seems to answer your question: there is no deterministic context-free language $L$ such that, for every deterministic context-free language $C$, there ...

8

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 power of an auxiliary pushdown store—it is however hardest w.r.t log-space reduction. The language $L_0^{(2)}$ referred therein is the set of words over $... 8 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 as$h^{-1}(L_0)$or$h^{-1}(L_0-\{e\})$for a homomorphism$h$. The algebraic statement is: the family of context-free languages is a principal AFDL; ... By ... 8 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$-state DFAs over an alphabet of size$k$is $$d=d(n,k) := (k-1+o(1))n\log_2 n.$$ It follows that there are at least$2^d$distinct$n$-state automata on a$k$-... 8 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 you fix the model, you can only compute$2^k$functions that have a$k$bit description. 2) For uniform classes like P this is more challenging, as there is no ... 7 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 the definition by doing away with a complicated output function and having our machines simply give “yes” or “no” answers. This was also used by Myhill, ... 7 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 ensures a precise match with PCF (int its call-by-name variant -- changing to call-by-value is easy). In (4) the typing system gives a precise interpretation ... 7 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 any ideas. :) Initial Idea: One way to solve Triangle Finding is to find all pairs of vertices that are connected by a path of length 2. Then, you check if ... 6 This concept is called the ambiguity of the NFA. Typically, there are 3 classes of ambiguity in this context: Bounded, polynomially bounded, and exponentially bounded. Every NFA has at most an exponential number of runs on a given word (this is easy to see). Interestingly, there is a simple syntactic characterization of polynomially bounded NFAs: An NFA ... 6 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 deterministic computation like$\mathsf{DTime}(n^4) \subseteq \mathsf{NTime}(n)$holds. For the sake of contradiction, assume that$\mathsf{SAT} \in \mathsf{...

6

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. I don't know of any efficient simulation of deterministic machines by non-deterministic ones, but I know of several speed-up results that could be used if ...

6

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 simultaneously keep track of all possible runs of the $n$-state automaton, by moving around $n$ tokens. But we could decide to follow only $k<n$ runs, and do ...

6

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 follows. The $n$-bit input to the NFA is treated as an assignment to $x_1,\dots,x_n$. The NFA first nondeterministically selects one of the $m$ clauses. Then, it ...

6

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)\mid x_{p_i}=1 \forall i\}$. It should follow from some standard one-way communication complexity bound that $BACKPOINTER$ needs at least $t$ bits of memory ...

5

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 remains NP-complete even if variables are represented in unary. In particular we can convert a clause - suppose $(x_i \lor \neg x_j \lor x_k)$ - of an arbitrary 3-SAT ...

5

The following paper reports on an implementation of the Kameda-Weiner algorithm for computing a minimal NFA, as well on an approach using a SAT solver. I don't know whether the implementation is available, but perhaps you can contact the authors about this. Jaco Geldenhuys, Brink van der Merwe, and Lynette van Zijl. Reducing Nondeterministic Finite Automata ...

5

I think that the answer is the affirmative. Maybe there is a simpler proof, but here is a sketch of a proof which uses linear algebra. Like domotorp, we will view a configuration of an n-state XOR automaton as a vector in V=GF(2)n. Let L be a finite language over an alphabet Σ={1, …, k}, and consider an XOR automaton for L with the minimum number of ...

5

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 Logtime computation path has $O(\log n)$ single-bit interactions with the query tape(s); and as you note, to answer the question, it suffices to be able to (...

4

I think I can prove that cycles do not help over the unary alphabet. Consider the matrix $M$ over $F_2$ describing from which state into which state we can get in one step and the vector $v_n$ over $F_2$ describing the possible states of the automaton $\mod 2$ after $n$ steps, so $v_n=M^nv_0$, where $v_0=(1,0,..,0)$ describes the starting state. If we know ...

4

(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 languages accepted by finite automata with n states” (2002, M. Domaratzki, D. Kisman, J. Shallit). In this paper: the $f_{|\Sigma|}(m)$ function provides the ...

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