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. ...
Ryan Williams's user avatar
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 ...
Scott Aaronson's user avatar
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 ...
Emil Jeřábek's user avatar
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 ...
Joe Bebel's user avatar
  • 2,295
10 votes
Accepted

Converting 2-ambiguous NFA to unambiguous NFA

I think that this is in fact not possible, thanks to the (recent and difficult!) ICALP'22 results of Göös et al.. They show that there are UFAs $A_1$ and $A_2$ with $n$ states such that the language $...
a3nm's user avatar
  • 8,896
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 ...
Lance Fortnow's user avatar
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) ...
J.-E. Pin's user avatar
  • 4,771
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 ...
Michaël Cadilhac's user avatar
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 ...
Mateus de Oliveira Oliveira's user avatar
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$-...
Aryeh's user avatar
  • 10.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 ...
Martin Berger's user avatar
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 ...
Michael Wehar's user avatar
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 ...
D.W.'s user avatar
  • 11.7k
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)\...
domotorp's user avatar
  • 13.9k
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 ...
Denis's user avatar
  • 8,598
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 ...
Kaveh's user avatar
  • 21.5k
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....
Michael Wehar's user avatar
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 ...
Marzio De Biasi's user avatar
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 ...
Emil Jeřábek's user avatar
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 ...
Dmytro Taranovsky's user avatar
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 ...
Hiroki Morizumi's user avatar
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 ...
Luz's user avatar
  • 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 $...
Shaull's user avatar
  • 5,531
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 ...
Or Meir's user avatar
  • 5,350
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), ...
Boson's user avatar
  • 560
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 ...
Siddharth's user avatar
  • 803
2 votes

What is formal definition of non-deterministic algorithm in context of primitive/general recursion?

You could easily make Kleene's $\mu$-recursive programs nondeterministic. A $\mu$-recursive program consists of a sequence of function symbols, each defined from previous ones by composition, ...
Siddharth's user avatar
  • 803
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 ...
deong's user avatar
  • 804

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