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
1answer
42 views

If anything can be verified efficiently, must it be solvable efficiently on a Non-Deterministic machine?

Suppose, I wanted to verify the solution to $2$^$3$. Which is $8$. The $powers~of~2$ have only one 1-bit at the start of the binary-string. Verify Solution Efficently ...
1
vote
0answers
55 views

Question about proof of Lemma 2.41 - Sipser book

Doesn't the modification described in paragraph three potentially introduce non-determinism? For example, say neither a, b, x, nor y is the empty string (denoted e). If in the original machine P we ...
1
vote
1answer
28 views

Conversion of nfa with self-loop to one without self-loop

For every nondeterministic finite state automata that has self-loop(s), there exists an equivalent nfa that does not have any self-loop. How can we prove this statement in a general basis without the ...
0
votes
1answer
32 views

Non Deterministic Turing Machine

Can anyone give an example of a NDTM for a problem (which cannot be solved with DTM) with transition function?
0
votes
2answers
60 views

In a NPDA if the stack is empty, where the start/end state are the same can you go again

Thoughts I am wondering if you get a string that goes through the NPDA and arrives back at q0 can I go through the NPDA again so that the last number in the string is not fixed, or is it that once I ...
3
votes
1answer
54 views

Arden's Rule, DFA & NFA to regular expressions

I have been trying to figure out the Arden's Rule and the equational method to transform DFA's & NFA's to RE. I know what the rule state: if x = s + xr then x = sr*, with $s,r\in$ Regular ...
1
vote
1answer
39 views

Is $L \subset 1NL$ when $L \neq NL$? [closed]

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 ...
-1
votes
1answer
86 views

Constructing an NFA for a language defined over $\Sigma = \{0, 1\}$

The language is defined as $$L = \{0^n10^m10^q \mid n,m,q \in \mathbb{N}, q \equiv nm \mod 5\}.$$ Can someone help me get started on this question? I don't know what part of the question I should do ...
-1
votes
2answers
70 views

Why is nondeterminism physically not realizable?

Why it is so hard to make a nondeterministic computer? If such a device is physically realizable then would that be a counterexample to the extended Church-Turing thesis?
0
votes
0answers
55 views

apply the method of conditional expectations

For a Randomized vertex cover problem Why there is not much hope of deriving an efficient, deterministic version using the method of conditional expectation? I can assume the problem is not ...
0
votes
0answers
21 views

Problem in NP: $EQ1 = \{(p_1,…,p_n): \exists x_1,…,x_m\in Z \ p_1(x_1,…,x_m)=…=p_n(x_1,…,x_m)=0. \}$

I have to following problem to show is in NP class. $EQ1 = \{(p_1,...,p_n): \exists x_1,...,x_m\in Z \ p_1(x_1,...,x_m)=...=p_n(x_1,...,x_m)=0. \}$ Here $p_1,...,p_n$ are polynomials in m ...
1
vote
1answer
28 views

Non-deterministic Turing machine for $L_1 = \{w\#0^n|w \text{ is a suffix of some $x$ in $L$ with } |x|=n\}$

Show if L is in NP, then also L1 is in NP $$L_1 = \{w\#0^n|w \text{ is a suffix of some $x$ in $L$ with } |x|=n\}$$ I know that if L is in NP, then there exists a NTM $M_L$ than accepts $x$, ...
1
vote
1answer
47 views

What is $f(n)$ in $NTIME(n)\subseteq DTIME(f(n))$ if $CIRCUITSAT$ is in $P$?

If $CIRCUITSAT$ in $n$ variables and $m$ gates has an $O((nm)^c)$ algorithm for a fixed $c>0$ then $NTIME(n)\subseteq DTIME(O(f(n)))$ for large enough $f(n)$. What is the smallest $f(n)$ in $NTIME(...
0
votes
0answers
18 views

Proving a problem is NP [duplicate]

I've seen in many textbooks if say we have a problem $Q$, we write a non-deterministic algorithm in polynomial time to solve problem $Q$, and then from that point it results that $Q\in NP$. Why is ...
1
vote
1answer
142 views

How to prove Shortest Common Superstring is NP-Hard

After some research and many youtube videos I have learnt that to prove a problem is NP-Hard; you would need to reduce that problem to known NP-Hard problems such as Subset Sum Problem, Halting ...
0
votes
0answers
14 views

Push Down Automatas: Is it still an accept state if stack is not empty?

I'm currently seeing if a PDA is in an accept state give an input string. After reading the entire input tape, I am currently in the accept state. However, in the stack, there are two items in it. So ...
2
votes
1answer
78 views

If A and B are NP-complete, then A ∪ B need not be NP-complete

I am studying the proof of this exercise (link) There exist N P-complete languages A and B such that A ∪ B is not N P-complete. Example: $A = \{1x : x ∈ SAT\} ∪ \{0x : x ∈ \{0, 1\}^∗\};$ $B =...
2
votes
1answer
59 views

Converting non-deterministic algorithm to deterministic

I was thinking about an non-deterministic algorithm to generate all the subsets of the $\{1..n\}$ set. ...
0
votes
1answer
296 views

How to prove Exact cover problem is NP Complete using Vertex Cover problem?

Using reduction theorem in NP, we want to prove that Exact cover is NPC by reducing it from Vertex Cover Problem. It is easy to derive it from SAT, but we can't find a solution yet to derive it from ...
4
votes
1answer
346 views

How to determine if a language is deterministic context-free language?

I have the following question to solve : DCFL means Deterministic Context-Free Language. Let $L$ be a DCFL over an alphabet $\Sigma$. For each of the following functions of $L$, determine whether $...
5
votes
2answers
109 views

motivation and idea of defining non-deterministic Turing machine

This is a very basic question but I spent some time reading and find no answer. I am not computer science majored but have read some basic algorithm stuff, for example, some basic sorting algorithms ...
1
vote
3answers
295 views

NFA for all strings not containing 1010

if I want to design a NFA (that's NOT A DFA) that accepts the set of all strings that do not contain the substring 1010, is this correct? because I can just accept 1010 by capturing it in the starting ...
3
votes
0answers
42 views

Minimal regular expression from minimal NFA for finite language in polynomial time?

Given a minimal NFA for a finite language, is there a polynomial-time algorithm to find a minimal regular expression for the same language? This question is based on a recent question regarding ...
0
votes
0answers
63 views

Why is it not possible to prove the equivalence of nondeterministic and deterministic Turing Machines the same way as for NFAs and DFAs?

I found en excercise asking this question. I know that for proving the equivalence of NFAs and DFAs we can use the conversion through subsets, and that for proving the equivalence of nondeterministic ...
2
votes
1answer
67 views

Like transitive reduction, but removing vertices rather than edges?

Suppose I have a directed graph $G = (V, E)$ (or, which is the same, a relation on the set $V$ as defined by the adjacency matrix) that may contain three vertices $x, y, z$, such that $xy, xz, yz \in ...
1
vote
1answer
194 views

How to make Turing machine deterministic?

My Turing machine starts with an empty tape. It writes a random word of the set $0^n1^n$ to the tape. Hopefully i made no mistakes. My question is about the productions coming out of state $q_0$: $δ(...
6
votes
1answer
55 views

What publication first introduced the concept of a non-deterministic Turing machine?

What publication first introduced the concept of a non-deterministic Turing machine? Turing did not define the concept in his 1936 paper.
0
votes
1answer
55 views

TQBF PSPACE-COMPLETE : Why this algorithm is exponential but Savitch's not?

So this is a question pertaining to the proof for $PSPACE-COMPLETE$ (for TQBF for example). The idea is to first prove the $L$ $is$ $PSPACE$(easy part) and next is to prove $PSPACE-COMPLETE$. The ...
0
votes
1answer
51 views

Why does NTM need to derive certificate to prove “If a language is in in NP iff it is decidable by some nondeterministic polynomial time TM”?

(Sipser's Chapter 7: Time COmplexity, Pgs 294-295) If we have to prove the forward direction, then we must have the certificate along with the verifier. I don't get why we are "guessing the ...
1
vote
2answers
122 views

Why is the run time of an $f(n)$ space decider bounded by $2^{O(f(n))}$?

In the proof of Savitch's theorem from the 3rd edition of Sipser's Intro to Theory of Computation, Sipser claims that the maximum time that an $ f(n) $ space nondeterministic Turing machine that halts ...
2
votes
2answers
53 views

Given an non-deterministic finite automaton, will its determinization always have unreachable states?

Given an NFA that accepts the regular language L, will its equivalent DFA which accepts the same language L always have unreachable states. If it does, why?
1
vote
0answers
27 views

How to adapt proof of the ND time hierarchy theorem for alternate definition of NDTM?

For reference, the version of the nondeterministic time hierarchy theorem in question is this one: The relevant portion of the proof in question (also from Arora-Barak) is here: Arora-Barak define a ...
2
votes
1answer
59 views

NL problem? $CONN$= {$〈G,k〉$ ∶$G$ is undirected graph with at least k connected components}

Consider the following decision problems: $CONN$= {$〈G,k〉$ ∶ $G$ is undirected graph with at least $k$ connected components} $E-CONN$= {$〈G,k〉$ ∶ $G$ is undirected graph with exactly $k$ connected ...
3
votes
1answer
107 views

Is the halting problem solvable for NPDAs?

After the total silence in response to my last question, I am rethinking my assumptions. DPDAs are, of course, solvable, and I believe that their loops can be found in the manner I described in my ...
9
votes
1answer
1k views

Non-deterministic Finite Automata | Sipser Example 1.16

I am working through the Sipser Book (2nd edition) and came across this example, which I do not understand. In the book it states that this NFA accepts the empty string, $\epsilon$. Could someone run ...
4
votes
0answers
92 views

Detecting loops in NPDAs

I'm aware that the halting problem is solvable for PDAs, but I have recently discovered that I am wrong about how to actually do it. I used to think that you could detect an infinite loop by meeting ...
3
votes
2answers
76 views

In what sense are dataflow architectures non-deterministic?

The Wikipedia article mentions non-determinism in the context of dataflow architectures. Arthur Veen's paper mentions non-determinism when it elaborates on MERGE nodes as conditional constructs. Are ...
2
votes
1answer
49 views

Why “Choice Points” introduce non-determinism in a program?

I'm studying the didactic programming language Oz, following the book "Concepts, Techniques, and Models of Computer Programming". In the book, the nondeterminism is introduced through the concept of ...
0
votes
1answer
243 views

What's the purpose of the non-deterministic Turing machine?

(*) Acronyms NTDM := non-deterministic Turing machine. TM := deterministic Turing machine. (*) Consider the following idea The NTDM is able to follow, in parallel, all paths of the tree of the ...
1
vote
2answers
213 views

Describe in words how a NTM can simulate a DTM

I have this assignment Describe in words how a DTM can simulate a NTM Describe in wordshow a NTM can simulate a DTM I'm working on this request and I'm crushing with the comparison. 1-I ...
1
vote
0answers
46 views

Characterization of NFA whose equivalent (minimal) DFA has exponential number of states

(I don't know if there are standard names for this, so) Let's say that a Nondeterministic Finite Automaton (NFA) is $n$-expansive if it has $n$ states and any Deterministic Finite Automaton (DFA) ...
5
votes
1answer
153 views

If NP is a subset of DTIME[n^O(log n)] then what happens?

If $\mathsf{NP}\subseteq \mathsf{DTIME}[n^{O(\log n)}]$ then what happens? Does it imply $\mathsf{NP}\neq \mathsf{EXP}$? Is there any other consequences such as $\mathsf{BPP}\neq \mathsf{EXP}$? Does ...
2
votes
2answers
111 views

Why cannot we enumerate all Turing machines that have no fixed point?

The language $$ L_1 = \{w \in \{0, 1\}^\ast \mid \exists x \in \{0, 1\}^\ast\colon M_w(x) = x\} $$ ($w$ is an encoding of a DTM, $M_w$ is the respective DTM.) is not decidable, according to Rice's ...
7
votes
0answers
84 views

Automata that is Turing complete if you add a nondeterminism

Pushdown automata have an interesting property: non-deterministic ones belong to a different computational class than deterministic ones. This is in contrast to finite state and turing machines, for ...
1
vote
1answer
132 views

How do I construct a NTM that accepts the language consisting of the coding of turing machines that halt on one input?

I currently have a problem with the following question: Let $L = \{ \langle M \rangle \mid \exists w: \text{$M$ halts for $w$ in at most $|w|^3$ steps} \}$. Construct an NTM (non-deterministic Turing ...
5
votes
1answer
151 views

The definition of weakest precondition for a non-deterministic language

In the classical IMP language, the definition of weakest precondition is: definition "wp c Q s ≡ ∃t. (c,s) ⇒ t ∧ Q t" This is stating that from state s, after ...
3
votes
1answer
167 views

The Law of Excluded Miracle in the language of guarded commands

The definition of weakest precondition is familiar (let me use Isabelle's syntax here): definition "wp c Q s ≡ ∃t. (c,s) ⇒ t ∧ Q t" the weakest precondition ...
1
vote
2answers
807 views

What to do with empty set during NFA to DFA conversion?

I am currently converting this NFA to a DFA I have come up with the following DFA: ...
1
vote
2answers
107 views

Understanding Hamiltonian Path, NP vs Co-NP

I am having difficulty understanding the distinction between NP and Co-NP. According to my textbook (Sipser), the HAMPATH problem is in NP. That is, for the language: HAMPATH = { (G,s,t) | G is a ...
1
vote
1answer
1k views

PDA of the language where the number of a's are NOT equal to the number of b's

I have this NPDA for language L = {w: num_a(w) == num_b(w)} all loops in q1 ...

1
2 3 4 5 6