37

For one, proving $BPP \subseteq NP$ would easily imply that $NEXP \neq BPP$, which already means that your proof can't relativize. But let's look at something even weaker: $coRP \subseteq NTIME[2^{n^{o(1)}}]$. If that is true, then polynomial identity testing for arithmetic circuits is in nondeterministic subexponential time. By Impagliazzo-Kabanets'04, ...


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.


22

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,...


21

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

Any problem has such a version, just PAD it! E.g. the language that consists of a true 3CNF of length m followed by m^2 0's is in DSPACE(sqrt(n)).


14

The planar version of many NP-complete problems belong to $NTISP(n,n^q)$ for some $q<1$ See for example "Lower Bounds and Complete Problems in Nondeterministic Linear Time and Sublinear Space Complexity Classes" by P. Chapdelaine and E. Grandjean (2006)


14

Jean Berstel maintains a website with Schützenberger's collected papers. You can access the original paper (in French) here. A definition of the unambiguous product you are referring to in English is given by Pin in Syntactic Semigroups, p.30: "The product $L = L_0a_1L_1 \cdots a_nL_n$ is unambiguous if every word $u$ of $L$ admits a unique factorization of ...


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 [1948] and De Leeuw, Moore, Shannon and Shapiro [...


11

For any language in $\mathsf{NP}$ there exists a proof that can be verified using $O(\log n)$ working space. One just needs to use the same ideas used to prove SAT is $\mathsf{NP}$-complete. By definition, given an $\mathsf{NP}$ language $L$, we know that there exists a turing machine $M$ such that for any $x \in L$ there exists a $y$ such that $M(x, y)$ ...


11

Nondeterministic computations can also be viewed as verification of claims using short proofs. That is, the class NTIME(t) can also be viewed as the class of languages $L$ such that a claim of the form $x \in L$ can be verified in time $t(|x|)$ by reading a short proofs. In this model, "quantifying the braching" is analogous to studying how short the proofs ...


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

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

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

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

A polynomial amount of nondeterministic bits is enough to encode the computation of a nondeterministic polynomial time algorithm. The only thing we need is to check if a given string is an accepting computation which is syntactic task that can be performed by a polynomial-size $\mathsf{AC^0}$ circuit (in fact a polynomial size CNF can do this). Another way ...


7

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 $...


7

According to Ishigami Y., Tani S. (1993) The VC-dimensions 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$-...


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

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

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

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

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


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

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


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