All Questions
Tagged with complexity-theory nondeterminism
92 questions
2
votes
1
answer
76
views
Complexity of identifying "generic & distinguishable" Moore machines
Consider a non-deterministic Moore machine with input alphabet
$\Sigma
\newcommand\OO{\mathcal{O}}
\newcommand\o{\mathfrak{o}}
\newcommand\PP{\mathcal{P}}$ and output alphabet $\OO$, a set of states $...
- 31
0
votes
1
answer
112
views
Is $\text{logCLIQUE}\in \texttt{NSPACE($\log^2(n)$)}$?
I inspired by this question, $$\text{logCLIQUE}=\{\langle G\rangle:\text{G=(V,E) contains a clique of size $\log(|V|)$}\}.$$
Here $G$ is an undirected graph and it can be assumed that the number of ...
- 23
0
votes
2
answers
58
views
How can one say solving one np-complete problem in polynomial proves that all np-complete problems can be solved in p?
I keep reading that we don’t know if p=np or if p!=np , but what is the basis for this universality?
This question is derived from this statement from the book Introduction to algorithms, third ...
- 1
-1
votes
2
answers
172
views
Will this proof method work for p vs np
Given, that NP is the class of all problems that a non-deterministic Turing machine can solve in polynomial time, and proving P = NP will prove that there is no difference between a non-deterministic ...
3
votes
1
answer
476
views
What role does the lower bound play in the statement of Savitch's Theorem?
Savitch's Theorem states that $\text{NSPACE}\left(f\left(n\right)\right) \subseteq \text{DSPACE}\left(\left(f\left(n\right)\right)^2\right)$ for any function $f\in \Omega (\log(n))$.
I don't ...
0
votes
0
answers
41
views
Graph with an exponential number of paths
I am looking at the language $F$ containing all $G,v_0,v_1$ s.t.:
$G$ is undirected
$G=(V,E)$
$v_0,v_1\in V$
$|V|=n$
There are $2^n$ paths between $v_0$ and $v_1$
I would like to prove that $F\notin ...
- 142
0
votes
0
answers
37
views
Equivalent definition of a PTNDTM?
$NP$ is the class of problems with a polynomial time non-deterministic turing machine which can determine whether an input is in a certain language or not. It can be seen as polynomial time ...
- 142
1
vote
0
answers
23
views
$\mathsf{NP}$ vs. $\mathsf{coNP}$ and sparse sets
Consider the following statement:
If there exists a sparse set of negative (the ones whose answer is no) instances $I$ such that for every negative instance $a$ ...
- 2,041
1
vote
1
answer
30
views
Is the set of languages with verifiers running in polynomial time equal to the set of languages decidable by an NTM running in polynomial time?
I have seen two definitions for the set $NP$. One is that it is the set of languages decidable by a nondeterministic Turing machine (NTM) running in polynomial time, and the other is that it is the ...
1
vote
1
answer
153
views
How to construct complement of NFA universality?
Given an input NFA, can one construct an NFA that is universal (that is, accepts all its inputs) if and only if, the input NFA isn't universal?
I tried to use the fact that NFA-universality is PSPACE-...
- 133
3
votes
0
answers
44
views
Given a complexity class C for problems which can be solved using exponential time and an exponential number of random bits. C ⊆ NEXP?
There must be a complexity class C that includes exactly the problems that can be solved in exponential time and having access to a truly random coin (which in turns implies that you will be able to ...
- 145
10
votes
4
answers
2k
views
Probabilistic methods for undecidable problem
An undecidable problem is a decision problem proven to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. I wonder if there are examples of probabilistic ...
- 231
1
vote
1
answer
203
views
Exact formulation of definition of $NP$, in relation to $R$
One definition for $P$ is the set of all languages that have a deterministic turing machine $M$ s.t. if $x\in A$ the machine accepts in polynomial time and otherwise it rejects, also in polynomial ...
- 142
2
votes
1
answer
240
views
A small issue regarding the proof of Savitch's Theorem
Savitch's Theorem states that $NSPACE\left( f \left( n \right)\right) \subseteq DSPACE\left( \left( f \left(n \right) \right)^2 \right)$ for any $f\left(n \right) \in \Omega \left( \log{n} \right)$.
...
- 142
1
vote
1
answer
167
views
Implications of Savitch's theorem
I'm trying to figure out if the following statements are true:
• Savitch’s theorem implies that $NSpace(\log n)$ = $DSpace(\log n)$.
• Savitch’s theorem implies that $NSpace(n^2)$ = $DSpace(n^4)$.
• ...
- 443
0
votes
0
answers
95
views
If P = NP then EXP^P = NEXP^NP?
I believe that if P = NP, then that would imply EXP = NEXP (because of the padding argument), and then EXP^P = NEXP^NP (we could replace EXP with NEXP since they are equal, and replace P with NP, ...
- 145
1
vote
0
answers
338
views
Confused about the concept of deciding in nondeterministic Turing machines
I read this discussion before.
However i’m still confused. I used to think a language decided by a NTM if for every input $w$ in $\Sigma^*$, all of the branches in computation tree leads to a halting ...
- 368
0
votes
0
answers
26
views
If a problem is Cook-reducible to a problem in NEXP, is it in NEXP too?
I get why that would be true for EXP but cannot extend the argument to NEXP.
2
votes
1
answer
80
views
Number of queries for $NP^{NP}$
So a few days ago my lecturer told us that for every nondeterministic polynomial time oracle
machine $M$, there is a nondeterministic polynomial time oracle machine $N$ that gives us $L(N^{3-SAT}) = L(...
- 121
0
votes
1
answer
309
views
Counting strongly connected components in a directed graph in $NL$
Define $K\_SCC = \{ \langle G, k \rangle \,:\, G \text{ has at least $k$ strongly connected components} \}$
I want to show that $K\_SCC \in NSPACE(\log n)$, using that $st-CONN$ and $\overline{st-CONN}...
- 1
1
vote
1
answer
84
views
Is there distinction between $(C/poly)\cap(coC/poly)$ and $(C\cap coC)/poly$?
Let $C$ be an uniform complexity class for example $NL$ or $NP$. Is there distinction between $(C/poly)\cap(coC/poly)$ and $(C\cap coC)/poly$?
- 2,919
0
votes
0
answers
25
views
Are there more succint algorithm for translating NFA's to DFA's?
When translating an NFA to its deterministic equivalent, we get an exponential blowup due to the powerset construction method. I tried to search but couldn't find an appropriate question regarding ...
- 321
2
votes
1
answer
1k
views
Polynomial time verification of Graph Isomorphism problem
Using guess and check method, for two given graphs with the same number of nodes, a NTM selects a permutation of the node set and then checks if the edges are preserved.
The nondeterministic selection ...
- 37
0
votes
1
answer
71
views
What is the relationship between the number of transition rules for an NDTM and the resulting number of computational branches?
How can an NDTM have a growing number of branches as you feed larger and larger inputs with only finite number of transition rules specified--ie what is the relationship between the number of branches ...
- 375
1
vote
1
answer
112
views
Is $NSPACE(S(n)) \subseteq DSPACE(S(n))$ if $S(n)$ is time-constructible?
I read from Savitch's theorem that given a fully space-constructible function $S(n)$, we have
$$
NSPACE(S(n)) \subseteq DSPACE(S(n)^2)
$$
Am wondering, what happens if $S(n)$ is fully time-...
- 481
2
votes
1
answer
546
views
State complexity of converting epsilon-NFAs to NFAs without epsilon transitions
I am well-aware of the result showing that one can convert an epsilon-NFA (that is, an NFA with epsilon transitions) $A$ to an NFA without epsilon transitions $A'$, where $L(A) = L(A')$.
Is there a ...
- 23
1
vote
1
answer
72
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
...
- 57
1
vote
1
answer
167
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 ...
- 83
1
vote
1
answer
123
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(...
- 111
1
vote
1
answer
2k
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 ...
- 13
0
votes
1
answer
188
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 ...
- 71
1
vote
2
answers
844
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 ...
- 363
1
vote
0
answers
166
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 ...
- 363
2
votes
1
answer
345
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 ...
- 387
5
votes
1
answer
805
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,919
2
votes
1
answer
56
views
In certificate view of NL can we force the guesses to be in some format like $a^n b^n c^n d^n$?
In certificate view of NL the size of our guess can be polynomial.Can this guesses be like $a^n b^n c^n d^n$. Can we force the guesses to be in some format? I think it(the format) can be in regex ...
- 537
3
votes
1
answer
67
views
How to prove existence of the language
Consider such question:
(Prove or disprove) There exists a language in $TIME(2^{n^2})$ that is not in $NTIME(n)$.
I guess that answer is yes because $TIME(2^{n^2})$ and $NTIME(n)$ are totally ...
0
votes
1
answer
132
views
Is this language NP Hard?
$L=\{$$($$m$,$w$,$n$$)$| $m$ is an encoding of a non-deterministic Turing machine, $w$ is any word/string in the closure of alphabet, i.e. $w\in\Sigma^*$, $n$ is any positive integer, i.e. $n\in\Bbb{Z}...
2
votes
1
answer
134
views
Questions on Sipser's NP implying verifiability?
I've revisited trying to understand the proof to why NTM exists iff there is a verifier. I think I'm finally understanding the proof but I want to make sure and thus have some questions as follow up ...
- 499
1
vote
3
answers
401
views
Is there a method to compress all data without loss (lossless compression)?
I know that the answer is no but I'm not sure why. Here's where I started. We know that all data with length $n$ Bits and minimum $1$ Bit can be compressed, either lossless or lossy. But how do I ...
- 463
0
votes
0
answers
196
views
show doubly connected graph is NL complete
The question:A directed graph is doubly connected if every two vertices are connected by a directed path in each direction. Let DCG = {| G is a doubly connected graph} Prove that DCG is NL-complete. (...
- 1
7
votes
1
answer
554
views
Implications of $NL=P$
What would be some implications of $NL$$=P$? Would it be possible to get recommendations on good sources/papers I can read to learn more about this? Thank you
- 71
14
votes
3
answers
1k
views
Why nondeterminism?
Theory of computation often involves nondeterministic models of computation. Some examples include nondeterministic finite automata (NFAs), nondeterministic pushdown automata (PDAs), and ...
- 279k
0
votes
1
answer
112
views
If all computations of non deterministic Turing machine on the input string are all accept then is the boolean formula of them a tautology?
If M is non deterministic Turing machine and w is any string then $\Phi_{M,w}$ is satisfiable if and only if M accepts w according to Cook and Levin (1971).
By the definition of non deterministic ...
user82913
0
votes
0
answers
38
views
How about boolean formula that is satisfied on every reject path and falsified on every accept path of non deterministic Turing machine? [duplicate]
Cook-Levin reduction is both deterministic polynomial time and parsimonious and that's mean that from every non deterministic Turing machine $M$ and string $w$ it is possible in polynomial time ...
user82913
-1
votes
1
answer
104
views
Relating accepting/rejecting paths to satisfying/falsifying assignments in (Cook, 1971)
I read The Complexity of Theorem-Proving Procedures by Stephen A. Cook (1971).
Cook explains how to create a boolean formula $\Phi$ from $(M,w)$, where $M$ is a non-deterministic Turing machine that ...
user82913
0
votes
2
answers
97
views
Does polynomial time reduction from CNFFAL to CNFSAT is also polynomial time reduction from CNFSAT to CNFFAL?
CNFSAT is the language of all strings that are encoding of satisfiable boolean formula in conjunctive normal form while CNFFAL is the language of all strings that are encoding of falsifiable boolean ...
user82452
2
votes
1
answer
280
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-...
- 2,919
0
votes
1
answer
93
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 ...
- 2,919
0
votes
1
answer
311
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 ...
- 225