Questions tagged [nondeterminism]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
2 answers
283 views

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

While preparing a class, I stumbled over a point that I could not elucidate. Explaining it requires a few step. Deciding vs Recognizing: A Turing machine $M$ decides a language $L$ if whenever $s\in ...
Arnaud Casteigts's user avatar
1 vote
0 answers
73 views

Are there any candidate languages in NE but not E?

Let ${\bf E}=\text{DTIME}(2^{O(n)})$ and ${\bf NE} = \text{NTIME}(2^{O(n)})$ Is there any candidate natural language being in ${\bf NE} \setminus {\bf E}$, that is, people believe is ${\bf NE}$ but ...
Eleonora's user avatar
5 votes
0 answers
126 views

"Interesting" problems in $NLogTime \cap coNLogTime$

In terms of machine model, I'm interested in multitape Turing machines with random access to the input via a query tape. Criteria for "interesting" in this context: Not in $DLogTime$: "...
Jake's user avatar
  • 1,214
7 votes
1 answer
342 views

Converting 2-ambiguous NFA to unambiguous NFA

This must be known, but somehow I can't locate a reference about this. Let $A$ be a nondeterministic finite automaton (NFA) over words of an alphabet $\Sigma$. I say that $A$ is unambigous if, for ...
a3nm's user avatar
  • 9,259
3 votes
2 answers
135 views

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

I want to understand general method for formally defining non-deterministic algorithm. But all formal definitions I see are related to FSM/Turing-machines. What is the reference for non-deterministic ...
uhbif19's user avatar
  • 315
-1 votes
1 answer
92 views

How is memory being used by an algorithm, to define its space complexity? [closed]

In computation we always talk about the time and space complexity of a given algorithm. The time complexity describes how long an algorithm takes in relation to the quantity of input it receives. ...
Cybernetic's user avatar
3 votes
0 answers
68 views

Exponential version of $CC^0$

(In this question, "uniform" will mean $DLOGTIME$-uniform.) In Allender's 1998 paper "The Permanent Requires Large Uniform Threshold Circuits", he talks about the "exponential ...
Jake's user avatar
  • 1,214
0 votes
0 answers
135 views

Savitch's theorem for time complexity

Is it known that an analog of Savitch's theorem for time complexity is impossible, or is this an open question? More formally, is $\exists d\ \forall c : \mathsf{NTIME}(n^c) \subseteq \mathsf{DTIME}(n^...
Nicholas Brandt's user avatar
3 votes
1 answer
206 views

Most non-deterministic automaton

My question is about how to construct, given a number n, an NFA with n states which gets converted to a complete (i.e., with no omitted transitions) DFA with exactly $2^n$ reachable states (even ...
user6767509's user avatar
0 votes
0 answers
45 views

Capturing a particular regular language with $O(m)$ states

In dx.doi.org/10.1006/inco.2001.3069 the authors defined $NID_m = \{ u\in \{0,1\}^* | \exists i : u_i \neq u_{i + m} \}$ and claimed it could be recognized by a NFA of size $O(m)$. The paper mentions ...
Alex Williams's user avatar
2 votes
0 answers
84 views

Result showing that DTIME[T] is strictly contained in random-access NTIME[T]

I recall seeing a result showing that multi-tape DTIME[T] is strictly contained in random-access NTIME[T] for reasonably large T (so not the PPST proof with the $\log^\star$ sort of factors), but I ...
exfret's user avatar
  • 643
9 votes
1 answer
223 views

Is the Triangle Finding decision problem in $coNTIME(\tilde{O}(n^2))$?

The Triangle Finding decision problem asks whether there exists a triangle in a graph $G$ containing $n$ vertices. A triangle is a triple of vertices $(a, b, c)$ such that $a$ is adjacent to $b$, $b$ ...
Michael Wehar's user avatar
16 votes
2 answers
510 views

NLOGTIME versus $\exists$DLOGTIME

$\def\dlt{\mathrm{DLOGTIME}}\def\nlt{\mathrm{NLOGTIME}}\def\mr{\mathrm}$During a recent discussion on another question, I mentioned a factoid $\exists\dlt=\nlt$, but then I realized that I may have ...
Emil Jeřábek's user avatar
1 vote
0 answers
109 views

On proving the standard $p$-measure on $NP$ assumption?

In the answer here An Anthology of Complexity Assumptions an interesting assumption is made. The assumption is $p$-measure of $NP$ is not $0$. There are many non-trivial consequences that follow from ...
Turbo's user avatar
  • 12.8k
6 votes
1 answer
256 views

Is $L \subset 1NL$ when $L \neq NL$?

A log-space Turing machine has a read-only input tape, a write-only output tape and uses at most $O(\log n)$ space in its read-write work tapes. The classes $L$ and $NL$ contain those languages which ...
Frank Vega's user avatar
10 votes
0 answers
175 views

Alternative proofs of Savitch's theorem?

Question: Are there any known proofs of Savitch's theorem that $NL \subseteq L^2$ besides the usual one? By the usual one I mean the proof based on recursively querying whether there is a midpoint. ...
Elle Najt's user avatar
  • 1,439
8 votes
1 answer
447 views

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

It is known that the problem of determining if an NFA accepts every word is PSPACE-COMPLETE, meaning it is also NP-Hard, but is this weaker version of the problem still NP-hard? Given an NFA and a ...
Tal K's user avatar
  • 113
8 votes
1 answer
341 views

Nondeterminism is on average useless for circuits?

Savický and Woods (The Number of Boolean Functions Computed by Formulas of a Given Size) prove the following result. Theorem[SW98]: For every constant $k>1$, almost all boolean functions with ...
Gustav Nordh's user avatar
  • 1,047
13 votes
1 answer
521 views

What are the obstructions to extending $L=SL$ to $L=NL$?

Omer Reingold's proof that $L=SL$ gives an algorithm for USTCON (In an Undirected graph with special vertices $s$ and $t$, are they Connected?) using only logspace. The basic idea is to build an ...
Alex Meiburg's user avatar
0 votes
1 answer
195 views

What do stronger circuit lower bounds give in terms of derandomization?

We have $EXP\not\subseteq P/poly\implies BPP\subseteq io-DTIME(2^{n^\epsilon})$ at every $\epsilon>0$. This is essentially $DTIME(2^{O(n)})\not\subseteq P/poly\implies BPP\subseteq io-DTIME(2^{n^\...
Turbo's user avatar
  • 12.8k
17 votes
1 answer
1k views

Example demonstrating the power of non-deterministic circuits

A non-deterministic Boolean circuit has, in addition to the ordinary inputs $x = (x_1,\dots,x_n)$, a set of "non-deterministic" inputs $y=(y_1,\dots,y_m)$. A non-deterministic circuit $C$ accepts ...
Gustav Nordh's user avatar
  • 1,047
7 votes
1 answer
759 views

Determinism and pi-calculus

Milner embedded $\lambda$-calculus into $\pi$-calculus, showing that the $\pi$-calculus is capable of Turing-complete, deterministic calculation. Since parallel compositions of processes in the $\pi$-...
Turion's user avatar
  • 616
8 votes
1 answer
1k views

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

Given a NFA $N$ and its equivalent DFA $D$ resulting from the total determinization of $N$ (using powerset construction, for example), the following properties hold for $N$, $D$ and for any word $w$ : ...
Luz's user avatar
  • 427
4 votes
1 answer
159 views

$NotTooManyP^{cc}$ class in communication complexity

Class $P^{cc}$ is class of languages admitting deterministic communication protocol with polylog bits of communication. Class $NP^{cc}$ is class of languages admitting nondeterministic communication ...
ivmihajlin's user avatar
10 votes
2 answers
480 views

Number of minimal DFAs of size at most $m$?

Let $\Sigma$ be an alphabet of size $2$, and consider minimal DFAs whose size is bounded by at most $m$. Let $f(m)$ denote the number of different such minimal DFAs. Can we find a closed-form ...
Luz's user avatar
  • 427
3 votes
1 answer
112 views

Size bound on Büchi automaton for complement

For a given Büchi automaton $\mathcal A = (A, Q, \delta, q_0, F)$ we define a congruence on $A^{\ast}$ by $$ \begin{array}{llll} u \sim_{\mathcal A} v & :\Leftrightarrow & \mbox{for all }s,s' ...
StefanH's user avatar
  • 2,077
1 vote
0 answers
199 views

Why is an automaton on finite words co-deterministic iff its transitions are co-deterministic

In the article Automata and semigroups recognizing infinite words an automaton is specified by $\mathcal A = (Q, A, E, I, F)$ where $I$ is a set of initial states and $F$ a set of final states, $Q$ ...
StefanH's user avatar
  • 2,077
4 votes
0 answers
176 views

Nondeterministic communication complexity of Hamming distance

It is something that I think should be known: what is nondeterministic communication complexity of following task: is $H(x,y) \geq k$? There is an obvious upper bound $k \log(n)$. I would expect ...
ivmihajlin's user avatar
9 votes
2 answers
262 views

Is a quadratic nondeterminism speed-up of deterministic computation plausible?

This is a follow up to nondeterministic speed-up of deterministic computation. Is it plausible that nondeterminism (or more generally alternation) would allow a general quadratic speed-up of ...
Kaveh's user avatar
  • 21.6k
14 votes
3 answers
582 views

Nondeterministic speed-up of deterministic computation

Can nondeterminism speed-up deterministic computation? If yes, how much? By speeding-up deterministic computation by nondeterminism I mean results of the form: $\mathsf{DTime}(f(n)) \subseteq \...
Kaveh's user avatar
  • 21.6k
12 votes
3 answers
470 views

Does there exist a hardest DCFL?

Greibach famously defined a language $H$, the so-called nondeterministic version of $D_2$, such that any CFL is an inverse morphic image of $H$. Does there exist a similar statement with DCFL, ...
Michaël Cadilhac's user avatar
5 votes
0 answers
196 views

Is anything known about Sokoban with only 1 box?

This is intended to be a simpler version of my earlier question here. In this post, 1-Sokoban-search is Sokoban with only 1 box, 1-Sokoban-decision is the corresponding decision problem, and 1-Sokoban ...
user avatar
14 votes
1 answer
650 views

How is the MA version of SETH proven to be false?

According to this paper, which discusses a nondeterministic extension of the Strong Exponential Time Hypothesis (SETH), "[…] Williams has recently shown related hypotheses about Merlin-Arthur ...
user avatar
19 votes
2 answers
2k views

Is there a non-deterministic linear time algorithm for CNF-SAT?

The decision problem CNF-SAT can be described as follows: Input: A boolean formula $\phi$ in conjunctive normal form. Question: Does there exist a variable assignment that satisfies $\phi$? I'm ...
Michael Wehar's user avatar
20 votes
3 answers
2k views

Who introduced nondeterministic computation?

I have two historical questions: Who first described nondeterministic computation? I know that Cook described NP-complete problems, and that Edmonds proposed that P algorithms are "efficient" or "...
user avatar
8 votes
1 answer
379 views

Hierarchy theorem for NTIME intersect coNTIME?

$\newcommand{\cc}[1]{\mathsf{#1}}$Does a theorem along the following lines hold: If $g(n)$ is a little bigger than $f(n)$, then $\cc{NTIME}(g) \cap \cc{coNTIME}(g) \neq \cc{NTIME}(f) \cap \cc{coNTIME}(...
William Hoza's user avatar
  • 1,733
7 votes
0 answers
616 views

complexity of Sokoban with a small number of boxes

(I asked a very concise version of this one month ago on cs.stackexchange, and although it got edited, it was not (otherwise) responded to.) In this post, for positive integer values $k$, "$k$-...
user avatar
27 votes
1 answer
2k views

Deciding emptiness of intersection of regular languages in subquadratic time

Let $L_1,L_2$ be two regular languages given by NFAs $M_1,M_2$ as input. Assume we would like to check whether $L_1\cap L_2\neq \emptyset$. This can clearly be done by a quadratic algorithm which ...
R B's user avatar
  • 9,448
4 votes
1 answer
315 views

minimal finite automata given in-words and out-words

this seems an interesting FSM optimization problem; have not seen it studied, wondering if it has been and/ or looking for other insight. given: two finite sets of words $S_{in}$ and $S_{out}$. ...
vzn's user avatar
  • 11k
15 votes
2 answers
598 views

Does XOR automata (NXA) for finite languages benefit from cycles?

A non-deterministic Xor automata (NXA) is syntactically an NFA, but a word is said to be accepted by NXA if it has an odd number of accepting paths (instead of at least one accepting path in the NFA ...
R B's user avatar
  • 9,448
6 votes
1 answer
191 views

Bounds on the size of NFA for $r$-skip $k$-distinct language

This question is about an extension of a language discussed in this question. We define the $r$-skip $k$-distinct language as follows: $$L_{r,k}=\{\sigma_1\sigma_2\cdots \sigma_{rk}\in\Sigma^{rk} | \...
R B's user avatar
  • 9,448
6 votes
1 answer
250 views

Halting time of non deterministic machine

Let $K$ be a non deterministic machine. I use Minsky Machine (2 counter automaton) for practical reason in my research, but it could be a turing machine, a register machine, whatever. The Machine ...
Arthur MILCHIOR's user avatar
5 votes
1 answer
4k views

What are the relationship and difference between ambiguous grammars and non-deterministic ones?

Intuitively, I had assumed that ambiguous grammars were roughly the same as non-deterministic grammars. According to Wikipedia however, this is false: there are non-deterministic unambiguous CFGs ...
Matt Fenwick's user avatar
8 votes
1 answer
206 views

Consequences of nondeterminism speeding up deterministic computation

If $\mathsf{NP}$ contains a class of superpolynomial time problems, i.e. for some function $t \in n^{\omega(1)}$, $\mathsf{DTIME}(t) \subseteq \mathsf{NP}$, then if follows from the deterministic ...
GMB's user avatar
  • 2,393
31 votes
1 answer
823 views

Can graph isomorphism be decided with square root bounded nondeterminism?

Bounded nondeterminism associates a function $g(n)$ with a class $C$ of languages accepted by resource-bounded deterministic Turing machines, to form a new class $g$-$C$. This class consists of those ...
András Salamon's user avatar
7 votes
2 answers
475 views

A tool for minimal NFA computation

It is well known that minimizing an NFA for a fixed regular language is $PSPACE-Complete$. As far as I know, there are no better than trivial algorithms for minimizing such NFA, but there's a little ...
R B's user avatar
  • 9,448
3 votes
0 answers
176 views

Deciding whether a binary multiplicity automaton has empty language

Multiplicity automatons (see here) is an interesting model. They have the (almost) same syntax as a non-deterministic finite automatons, but instead of deciding whether a word belongs to a language, ...
R B's user avatar
  • 9,448
10 votes
1 answer
502 views

Implications between $\mathsf{L}=\mathsf{P}$ and $\mathsf{NL}=\mathsf{NP}$?

If we can prove that $\mathsf{L}=\mathsf{P}$, does it imply that $\mathsf{NL}=\mathsf{NP}$ ? I thought it is the case, but I cannot prove it (also for the converse).
Thatchaphol's user avatar
  • 1,130
0 votes
0 answers
204 views

How to picture Non-Deterministic Turing machine seeking out boolean expression to satisfy examples

Traditionally, the boolean satisfiability problem is framed as, given a boolean formula, is there an assignment that satisfies the formula. I'm trying to look at this differently - from the ...
user375334's user avatar
12 votes
3 answers
342 views

Is there a reduction to "door and pressure plate" games that doesn't explode solution length?

This paper gives a proof that in a game with doors and pressure plates, it is PSPACE-hard to determine whether or not the (player's) avatar can reach a given location. This is proven by a reduction ...
user avatar