Questions tagged [nondeterminism]

Questions about automata, formal grammars or other computation-models that specifically relate to the use of nondeterminism. Not to be confused with randomness or ambiguity!

Filter by
Sorted by
Tagged with
1
vote
0answers
439 views

Comparing non-deterministic and also the deterministic expressive power of FA, PDA's and TM'S [closed]

I am sorta confused and also could not find a answer online, but in terms of expressive power, . Non-deterministic FA, PDA, TM NFA < NPDA < NTM ...
2
votes
1answer
111 views

On $NP=\Sigma_2^P$ from non-deterministic time?

We know $NP=\bigcup_{k\in\Bbb N}NTIME(n^k)$ and $\Sigma_2^P=NP^{NP}$. Does $\Sigma_2^P\subseteq\bigcup_{k\in\Bbb N}NTIME(n^k)$ also hold (we can do $O(n^k)$ queries to $NP$ oracle which runs in non-...
4
votes
3answers
778 views

What is difference between nondeterministic polynomial time and exponential time?

I am not very into computer science theory but i feel like people are defining nondeterministic polynomial time as if it is another name of exponential time. I would be happy if you clarify it. thank ...
1
vote
1answer
75 views

Are probabilisitc algorithms deterministic?

I got confused with deterministic and probabilistic algorithms. Am I right by assuming that algorithms are called probabilistic once they use some sort of randomness? Initially, I thought only ...
0
votes
1answer
75 views

On $UP$, $NP$, $\oplus P$ and $PP$?

We know $UP\subseteq NP\subseteq PP$. Is $UP^{\oplus P}\subseteq NP^{\oplus P}\subseteq PP^{\oplus P}$? I think the first $UP^{\oplus P}\subseteq NP^{\oplus P}$ is straightforward since whatever ...
0
votes
1answer
86 views

Closure of a CFL under specific operation

Consider the following operation on language $L$: $\mathrm{inv}(L) = \{ xy^Rz \mid x,y,z\in \Sigma^*, xyz\in L \}$ I understand that if $L$ is regular, then $\mathrm{inv}(L)$ is regular too, and ...
3
votes
1answer
215 views

Finding non-trivial NFA that accepts all short strings

It is well-known that every non-trivial NFA of $k$ states (an NFA that does not accept all strings) rejects a string of length at most $2^k$. But is this upper bound asymptotically tight ? I found ...
0
votes
1answer
139 views

$U = \{ \langle M, x, \#^{t} \rangle \vert M $ is a NTM that accepts $x$ within $t$ steps on some branch$\}$ is NP complete

I'm trying to prove $U = \{ \langle M, x, \#^{t} \rangle \vert M $ is a NTM that accepts $x$ within $t$ steps on some branch$\}$ is NP-complete. Showing it is NP is trivial. NP-hardness is the hard ...
0
votes
1answer
98 views

Behavior of non-deterministic Turing Machines after $t_i$ seconds

Suppose that I have a non-deterministic Turing Machine $M_1$ and its clone $M_2$. Given a string $x \in \Sigma^*$, it is possible that after $t_i$ seconds $M_1$ accepts $x$ and $M_2$ does not halt ? ...
0
votes
2answers
178 views

What is the deterministic finitite automaton (DFA) for the regex “.*b.”

I'm looking for a finite state machine that can match inputs to the regular expression .*b. deterministically (i.e. it cannot change state w/o being fed input and ...
1
vote
0answers
286 views

Non-deterministic Turing Machine recognizing a context-free Language

This question is taken from an exam of a Computer Theory Course. Describe how a NON-Deterministic Turing Machine with two tapes recognize the language generated from the grammar: $ S \rightarrow SS ...
1
vote
1answer
501 views

Non-deterministic 2-tape Turing Machine that recognizes palindromes in linear time

This question is taken from an exam of a Computer Theory Course. Describe how a NON-Deterministic Turing Machine with two tapes recognize in linear time palindrome strings with even length that ...
8
votes
1answer
968 views

Incorrect proof of closure under the star operation using NFA results in the NFA recognizing undesired strings?

I'm currently reading the book Introduction to the Theory of Computation (2nd or 3rd Ed.) by Michael Sipser, and have stumbled upon a question in Chapter 1 - Regular Languages, namely when the author ...
2
votes
2answers
332 views

What is the relationship between oracle Turing machine $M^O$ and Turing machine $M$ (given $O$)?

An oracle Turing machine (OTM) $\bar{M}$ can be denoted $M^{O}$ if it is a Turing machine (TM) $M$ with an oracle $O$. Given the oracle $O$, there exists a relation $R$ between OTMs and TMs such that $...
0
votes
0answers
52 views

How are Probability and Non Determinism Related ? Alternatives to handle Non determinism?

I have been thinking about Non-determinism in any kind of state machine. Since I work on machine learning, I tend to think that probability is a means of handling non-determinism. Instead of ...
3
votes
1answer
869 views

Working of NPDA

I read that acceptance of languages by DPDA using empty stack is a subset of languages accepted by DPDA using final state because of prefix property. I understood this statement by taking an example ...
0
votes
2answers
322 views

Why do the definitions of non-deterministic Turing machines look strange?

I read some definitions of the NDTM in several books. Something makes me confused. Some definitions say that the NDTM $M$ makes an arbitrary choice as to which of its transition functions to apply. ...
2
votes
1answer
178 views

What is the explicit definition about the computablity of non-deterministic Turing machine?

Given a finite alphabet $\Sigma$. We define the set of all words of finite length to be $\Sigma^{*}$. A partial function can become a total function with trivial modifications, thus we just consider ...
3
votes
0answers
39 views

Is it possible, at least in theory, to “lockfree-ize” algorithms algorithmically?

The problem emerged from a practical case, but thinking on it resulted more and more theoretical directions. Typically, the lock-free algorithms do relative simple things in the practice, but their ...
1
vote
1answer
102 views

NTM's and the halting problem

It is often stated that nondeterministic Turing machines cannot recognize any more languages than ordinary Turing machines. In particular, it is stated that there is no NTM that can take as input a ...
2
votes
1answer
953 views

STCON is NL complete - but why is the reduction in L?

I saw the proof for STCON being NL complete here : https://en.wikipedia.org/wiki/St-connectivity I understand the reduction, but how is it logspace? I understand each state is of $O(\log(n))$ space....
1
vote
1answer
288 views

Is a non-deterministic turing machine that both accepts and rejects the same input valid?

I.e. - if a TM accepts the word 0011100 on one path, while on another the same word is rejected. Do we say that 0011100 is part of the language, or do we say that it is not a valid TM?
15
votes
7answers
5k views

Why NFA is called Non-deterministic?

I have this [kind of funny] question in mind. Why is the non-deterministic finite automaton called non-deterministic while we define the transitions for inputs. Well, even though there are multiple ...
0
votes
0answers
83 views

Generating a Covering Array Matrix with Simulated Annealing

I've been reading the following paper to understand how I can develop a non deterministic algorithm for test cases generation https://www.researchgate.net/publication/293043297_A_two-...
12
votes
4answers
5k views

How does a nondeterministic Turing machine work?

What is differences between deterministic and nondeterministic Turing machines? Different but equivalent models of NDTM. In particular, what is this frequently used phrase "nondeterministically guess"?...
0
votes
1answer
52 views

Show that checking if there exists word not containg patterns from list is in $PSPACE$

There are given: alphabet $Σ$ with some symbols $a,b$. list of forbidden patterns Result: Is there exists word of form $a\Sigma^*b$ such that it doesn't contains (as subword) any of word from list ...
2
votes
1answer
746 views

Prove that $L$ is closed under Kleene star iff $L=NL$

Prove that $L$ is closed under Kleene star iff $L=NL$ Hi, I am trying to solve this exercise, but it is quiet difficult. Of course first part is very easy: Let assume that $L=NL$. Lets consider ...
2
votes
1answer
1k views

Question about NP problem certificates and P=NP

From my understanding a problem is considered to be in NP time if it can be solved in polynomial time with a non-deterministic Turing machine and verified in polynomial time with a certificate. My ...
0
votes
0answers
19 views

A recognizing “unique” words [duplicate]

By unique words we understand the such word $w$ that every character in the word occur at most once, for example: $\Sigma = \{a,b,c\}$ $w = abc$, $v = abca$ $w$ is unique, $v$ is not. Now, we have a ...
2
votes
2answers
3k views

NFA-epsilon: epsilon loops, and how do I deal with them?

I am currently studying Automatons and have one, albeit simple, question about NFA-epsilon 'loops' I know that a string can advance using epsilon without having anything read. So my first question ...
3
votes
1answer
451 views

Why we can't use non-deterministic turing machines in this case?

Can you explain me why we can't show decidability of problem using non-determinism ? I know that this problem (described below) is not decidability, however I can't understand why following reasoning ...
5
votes
2answers
831 views

Do NPDA work in parallel?

Assume my language is $$ L= ww^{r}\ $$ Now when we use NPDA for this,we will guess middle every time. It may be actual middle or it may not, so a new branch is created every time as I have a choice ...
7
votes
1answer
157 views

$\mathsf{NL}$ versus $\mathsf{NL}[2]$

There is an equivalent definition for the class $\mathsf{NL}$ with verifier. Those verifiers are deterministic Turing machines that can read the witness tape only once in one way from left to right. ...
2
votes
1answer
388 views

single tape NTM to single tape DTM equivalence

I am having some trouble understanding the equivalence of DTM's and NTM's. If you have Sipser its under 7.11; where he says that any NTM $N$ that halts after $t(n)$ steps has an equivalent DTM $D$ ...
3
votes
1answer
418 views

Understanding of SPACE in non deterministic Turing Machines

Let's consider the following situation. We have a finitie alphabet $A$. Let $A = \{a_1, .., a_k\}$ We consider words over $A$ of length exactly $n$. I am trying to solve some problem and I am going to:...
3
votes
1answer
71 views

Mapping many transition functions into two transition functions

Continuing from this answer: https://cs.stackexchange.com/a/56072/43035 I don't understand how it's possible to map many transition functions $\delta_1,...,\delta_n$ of a NDTM into just two ...
5
votes
1answer
186 views

Space-unconstructable function in the proof of Savitch's theorem

I'm learning about the Savitch's theorem, and while the construction proof is straightforward, I still don't understand one part about it. The proof I'm talking about is the same as is currently on ...
1
vote
1answer
282 views

Non-deterministic logarithmic time complexity class

Is that true that $Time(O(log(n)))=NTime(O(log(n)))$ iff $P=NP$? It seems to me to be true, as I only need to take log on both sides, since log of a polynomial is $O(\log(n))$, but I don't know how to ...
3
votes
3answers
747 views

Equivalence between alternative definitions of NP

I'm having some problems in understanding the two alternative definitions of NP. They're presented as equivalent, but to me they seem to define different class of problems. Intuitively, we can think ...
2
votes
1answer
914 views

Time Complexity OF NTM vs TM

In Sipser, It is given Pg. 284 Let t(n) be a function, where t(n) ≥ n. Then every t(n) time non-deterministic single-tape Turing machine has an equivalent 2 O(t(n)) time deterministic single tape ...
2
votes
1answer
35 views

Can Nondet Rabin Tree automaton be determinized?

In other words, are they equally powerful? (for word automata the answer is "yes"; this question is about tree automata). (i am talking about tree automata that work on $in$finite trees)
2
votes
1answer
244 views

When a NPDA is constructed from CFG, how many internal states will be used for accepting any string from the grammar?

Options given were: (a) 2 (b) 3 (c) 4 (d) 5 This question was a part of my assignment. I think the answer is 2 internal states - one start state and the other end state/acceptance state, but ...
0
votes
1answer
2k views

Product construction for given two finite automata

I need to construct a finite automata which accept a language $L = L_1 \cap L_2$, where $L_1$ and $L_2$ are given below. $L_1 = \{ w \mid w $ is divisible by 2 } $L_1 = \{ w \mid w $ is ...
6
votes
0answers
217 views

Why does Non Determinism not enhance FA like it does for PDA

Both Deterministic and Non deterministic Finite Automata can recognize the same universe of regular languages. On the other hand, Deterministic Push Down Automata can only recognize a subset of ...
3
votes
2answers
295 views

Puzzle/game of NP class for a high school student

Is there any puzzle or game which cannot be decided in polynomial time and whose problem description can be easily understood by a kid? If it is a fun puzzle so much the better. I want to demonstrate ...
0
votes
1answer
47 views

Bogo sort on NDTM

As we know on NDTM all the possible solutions for a given problem is verified the similar kind of work is done in bogo sort sequentially. So in future if an NDTM will be there. can we say it will be ...
1
vote
0answers
22 views

Why can't a server provide guaranteed service with only bounded nondeterminsm?

The wikipedia page Actor Model and Process Calculi History, presents the following claim: The semantics [of CSP] provided bounded nondeterminism unlike the Actor model with unbounded nondeterminism....
0
votes
0answers
140 views

Does for every NFA $N$ exist NFA $M$ that has maximum 3 final states and $L(N) = L(M)$

I have a question: Does for every NFA $N$ exist NFA $M$ that has maximum 3 final states and $L(N) = L(M)$. I can answer no for DFA for below language and its minimal DFA that has 4 final states . $...
1
vote
1answer
49 views

Is it possible to turn an eulerian NFA into a linear size DFA?

In general, there exists NFAs of size n whose smallest equivalent DFA requires 2^n states. But if we restrict ourselves to NFAs whose graph is eulerian, is it possible to turn any such NFA of size n ...
5
votes
2answers
689 views

Does the smallest DFA equivalent to this NFA requires at least $O(2^n)$ state?

The wikipedia page Powerset construction says that the DFA equivalent to this $(n + 1)$-state NFA (with $n=4$ here) "requires $2^n$ states, one for each $n$-character suffix of the input". I ...