Questions about relationships between complexity classes.

learn more… | top users | synonyms

3
votes
1answer
30 views

The class of languages that can be certified in a small amount of space

NP can be characterized in two different ways, one of them is that it's the class of languages that can be certified by a witness in a polynomial time. I wonder, if we consider the same notion but ...
0
votes
0answers
18 views

what is NP class? [duplicate]

I actually started to read complexity classes of problems. and I know that NP class include P class problems and even more problems call NP-complete ... as many books define NP class as well But I ...
1
vote
0answers
23 views

Why do we set conditions f(n) ≥ n resp. f(n) ≥ log(n) the Time resp. Space Hierarchy?

In the Space (Time) Hierarchy Theorem and also fully space (time) constructibility of two function we have the condition: being greater than $log(n)$ (being greater than $n$). Why do we have these ...
5
votes
2answers
345 views

Is DTIME(n) = DTIME(2n) true? (unlike Rosenberg's results)

I'm reading Homer and Selman's "Computability and Complexity" book. In some Corollary 5.3 it says: For all ε‎ > 0, DTIME(O(n)) = DTIME( (1+ε‎‎) n). Now I'm confused with this corollary and ...
4
votes
1answer
68 views

Known problems in BQP \ NP?

The introduction to Nielsen and Chuang has an Euler diagram of the suspected relationships between various complexity classes which shows $\text{BQP}$ extending slightly outside of $\text{NP}$. Is $\...
4
votes
1answer
180 views

Proofs of $P^{\#P}\subseteq P^{PP}$ and $\#P\subseteq FP^{PP}$

$P^{\#P}\subseteq P^{PP}$ and $\#P\subseteq FP^{PP}$ are known and usually handwaived as exercises. I could not find proofs of these two results. What is a rigorous proof for $P^{\#P}\subseteq P^{PP}$...
2
votes
1answer
112 views

Is NEXP = co-NEXP?

It is known that $\mathsf{NL}=\mathsf{Co{-}NL}$ and unknown if $\mathsf{NP}=\mathsf{Co{-}NP}$. But what about $$\mathsf{NEXP}=\mathsf{Co{-}NEXP}?$$ Is it known whether these two classes are equal?
1
vote
2answers
65 views

What does $\cdot$ mean as a notation with complexity classes?

In the wikipedia page for Toda's Theorem, the notation $A\cdot B$ is used where $A$ and $B$ are two complexity classes, but without explanation as to its meaning. SO given two classes $A$ and $B$ ...
3
votes
0answers
69 views

IS $LOGSPACE\subsetneq QMA$ an open problem?

Having read some chapters of Computational Complexity: A Modern Approach, I see no time or space hierarchy theorem which applies to this case. As far as I can see, we know the following inclusions: $...
2
votes
0answers
49 views

Are there theoretical reasons for believing that P=NP is harder than other complexity problems?

I have a meta-complexity question: Are there reasons to believe that it is more difficult to prove P != NP than, say PSPACE != EXPTIME or BPP != BQP?
9
votes
1answer
629 views

Why is NP in EXPTIME?

Is there an easy way to see why NP is in EXPTIME? It seems to me a priori conceivable that there could be a problem which requires super-exponential time to solve, but whose solution could be ...
1
vote
1answer
39 views

Short certificate analogy of PH?

We know that for problems in NP if the problem is an yes version then there is a short certificate and for coNP if the problem is a no version then there is a short certificate. Is there a short ...
-1
votes
1answer
50 views

Problem in computational complexity (superior class)

Say that a class $C_1$ is superior to a class $C_2$ if there is a machine $M_1$ in class $C_1$ such that for every machine $M_2$ in class $C_2$ and every large enough $n$, there is an input of size ...
0
votes
1answer
47 views

How to compute Jacobi symbol efficiently?

How do I compute the Jacobi symbol $(N|A)$ efficiently? In particular, for every odd $N, A$, define the Jacobi symbol $(A|N)$ as $\prod_i Q_{p_i}(A)$ where $p_1, \dots , p_k$ are all the (not ...
3
votes
1answer
53 views

A clarification on $PP$

Wiki in https://en.wikipedia.org/wiki/PP_(complexity) says "a PP algorithm is permitted to do something like the following: On a YES instance, output YES with probability $1/2 + 1/2^n$, where n is ...
3
votes
1answer
25 views

Maximal class for which function equivalence is decidable

I previously asked if it's decidable whether two primitive recursive functions are equivalent: "primitive recursive functional equivalence". The answer was no. Here is my followup. What is the most ...
7
votes
3answers
243 views

Relationship of algorithm complexity and automata class

I have been unable to find a graph depicting or text answering the following question: Is there a direct relationship between the complexity of an algorithm (such as best / worst case of quick sort), ...
2
votes
1answer
127 views

Polynomial hierarchy: inclusion between spaces

Using the definition for the polynomial hierarchy: $$ \Sigma_{i+1}^P = NP^{\Sigma_i^P} $$ $$ \Pi_{i+1}^P = coNP^{\Sigma_i^P} $$ I have been asked to to show that: $$ P^{\Pi_k^P } \subseteq \Pi_{k+1}...
5
votes
1answer
241 views

Select a subset of the columns in $2\times n$ matrix, is it easy?

I want to know if this problem is polynomial-time solvable or not? The problem is: Given a nonnegative integer-valued matrix of size $2\times n$ and two nonnegative integer numbers $b<n$ and $c$. ...
0
votes
0answers
36 views

What is an example of a problem that is in NP - P, but not NPC? [duplicate]

Assuming $P \neq NP$, I expected that $NP - P \subset NPC$, but from the diagram on Wikipedia it appears to not necessarily be true. What is an example of a problem that is complex enough to be in $...
3
votes
1answer
35 views

Randomized and Deterministic Communication Complexity of a function

I have a problem I'm trying to answer for my homework. The question is: Let $p$ be a prime number and let $GF(p)$ denote the finite field of size $p$. Suppose that A has input $x∈GF(p)$ encoded with $...
2
votes
0answers
60 views

Proving that AM contained in Pi_2

i think that it's true that AM is contained in $\Pi_2$ but I'm not sure how to prove it. How do I prove that $AM \subseteq \Pi_2$?
2
votes
1answer
73 views

2 SAT variants complexity class

Question: Which of the following languages are in P? which in NP? other classes? a. EXACTLY-2-CNF (every clause in the formula has 2 differenet literelas)- does there exist a satisfying assignment s....
-1
votes
2answers
45 views

Graph Isomorphism variant

Question: Given 2 undirected graphs $G_1$, $G_2$, the problem whether exists a subgraph H1 of G1 which is isomorphic to a subgraph $H_2$ of $G_2$. What is the lowest complexity class for this problem: ...
5
votes
1answer
569 views
2
votes
0answers
31 views

Do we have to overcome any barriers for a proof of $VP\neq VNP$ proof?

Does the same barriers of relativization, natural proofs and algebrization affect a possible $VP\neq VNP$ proof? How do existing strategies try to overcome these?
-2
votes
2answers
90 views

How to prove P ⊆ Co-NP

My approach Let L ∈ P $\exists$ Turing Machine $M_1$ which decides L. We can easily construct $M_2$ which decides $\bar{L}$ $\bar{L}$ ∈ CO-NP $\implies$ P ⊆ Co-NP I'm not sure ...
-2
votes
1answer
68 views

On equivalences to promise problem

We know that under hierarchy collapse results GI is not NP complete. Would there be any consequences if GI is equivalent to a promise version of an NP complete problem?
1
vote
1answer
33 views

Definition of complexity classes?

My book uses this definition for the Polynomial complexity class ($L$ is a language over $\{0,1\}$): $$\mathrm{P} = \left\{L\subseteq\{0,1\}^*\;\middle|\; \begin{array}{l} \text{there exists an ...
3
votes
1answer
51 views

is Co-NP in PSPACE?

Is Co-NP in PSPACE? I think it should obviously be, but I just wanted to make sure. I can find that NP is in PSPACE in Internet, but not on Co-NP.
3
votes
2answers
130 views

Proof of APSPACE = EXP

I have been reading Computational Complexity A Modern Approach book and this proof wasn't given in the book. Please give a semi-detailed proof of this. I have found a paper which has this proof(by ...
2
votes
1answer
37 views

Consequence of NP=coNP to some hierarchy problems

If $NP=coNP$ does it hold that $P/Poly=PH/Poly$ and/or $NP\subseteq P/Poly$ and/or $VNP=VP$? What can we legitimately say if $NP=coNP$?
4
votes
1answer
81 views

space complexity of DFA intersection problem

the DFA-intersection computation problem, given two DFAs specified on the input, compute the intersection DFA, or the decision problem to determine its emptiness, turns out to have wider/ deeper ...
1
vote
1answer
99 views

$\mathbf{NC_2}$ is closed under log-space reduction

I actually have to prove the following : $\mathbf{NL} \subseteq \mathbf{NC_2}$ I have the following approach : I will prove that $\mathbf{PATH} = \{〈D, s, t〉 | \text{D is a directed graph with a ...
1
vote
1answer
82 views

How to prove membership of NP [duplicate]

My tutor often says that proving membership of NP is the easy part of proving that a problem is NP-complete, and that this should only take a minute. What I don't understand is what exactly you're ...
5
votes
1answer
117 views

Simpler proof of Rabin's Compression Theorem?

I was doing a presentation on Rabin's Compression Theorem, when someone in the audience brought up a point I have no answer to. Rabin's Compression Theorem states that every reasonable complexity ...
4
votes
2answers
86 views

Can NP-Hard be converted to NP?

I get that all problems in NP can be reduced in polynomial time to some NP-Hard problem. An NP-Hard problem is also supposed to be harder or at least as hard as any NP problem. Can an NP-Hard problem ...
4
votes
1answer
39 views

What are the definitions for “hard problem” and “easy problem”?

Take for example the following sentence: Computing a hash for a message is "easy"; retrieving the message from the hash is "hard". Intuitively, I can perfectly understand what's written there. ...
3
votes
1answer
95 views

ZK proof that I possess a ZK proof for membership in $L$?

A zero-knowledge proof system for a language $L$ is an interactive proof system where a prover $P$ (a Turing machine) tries to convince a verifier $V$ (a polynomially bounded Turing machine) in a ...
1
vote
0answers
47 views

Monotone formulas versus Monotone Circuits [closed]

Are monotone formulas (formulas using positive constants, additions and multiplications) more powerful than monotone circuits? Are there illustrative examples?
2
votes
2answers
112 views

Why is $P \subseteq NP$?

The Clay paper gives a short proof on this in page 2: http://www.claymath.org/sites/default/files/pvsnp.pdf However, Where does it come from that these are inclusive sets and not separate? Or that $|...
4
votes
1answer
176 views

Prove or disprove that $NL$ is closed under polynomial many-one reductions

If $B \in NL$ and there exists a Karp reduction (polynomial-time many-one reduction) from $A$ to $B$, then $A \in NL$. Prove that the above claim is correct, incorrect, or equivalent to an open ...
1
vote
1answer
49 views

Prove that $coRP \subseteq RP^{RP}$

I've read in an article that $coRP = RP$ is an open question, but that it is obvious that $coRP \subseteq RP^{RP}$. If $L \in coRP$, I don't understand how access to the oracle helps to build a ...
2
votes
1answer
103 views

Implications of $NP = \Sigma_2 P$ for PH collapse

A simple fact is that $P = NP \to P = coNP$, which follows from the observation that $P$ is closed under complement. I am having trouble seeing that an analogous statement is true at higher levels of ...
5
votes
2answers
163 views

Complexity of “given a graph $G$ with vertex $v$, is there a maximum clique containing $v$”?

The usual way of translating the maximum clique problem into a decision problem is to ask "does there exist a clique of size $\ge k$ in $G$?" Clearly this problem is in NP (and is NP-hard). Another ...
0
votes
1answer
98 views

Consequence of $\mathsf{NP\subseteq BPP}$ to $\mathsf{NP\subseteq ZPP}$?

If $\mathsf{NP\subseteq BPP}$, then we know that $\mathsf{NP\subseteq RP}$ (http://www.csie.ntu.edu.tw/~lyuu/complexity/2011/20120103s.pdf). Does $\mathsf{NP\subseteq BPP}$ also imply $\mathsf{NP\...
2
votes
0answers
80 views

Relations between P^#P, NP^#P and (CO-NP)^#P

I was wondering if there were relation between the complexity classes $P^{\#P}$, $NP^{\#P}$, $(Co-NP)^{\#P}$ ?(except the trivial inclusions) I've the feeling that when taking a $NP^{\#P}$ machine, ...
4
votes
1answer
312 views

Why do reductions to NP-complete problems in NTIME(n) not break the nondeterministic time hierarchy?

Let $\mathrm{L} \in \mathrm{NTIME}(n^3)$. Since $\mathrm{NTIME}(n^3) \subseteq \mathrm{NP}$, we have that $\mathrm{L} \le_p \mathrm{3SAT}$. However, $\mathrm{3SAT} \in \mathrm{NTIME}(n)$. Hence, $\...
0
votes
0answers
55 views

Existence of randomized reduction but no deterministic reduction

What is the consequence to complexity theory of having a randomized reduction from an NP-complete problem to problem $\Pi$ while there is no deterministic reduction from an NP-complete problem to ...
3
votes
1answer
63 views

P/Poly class - undecidable lanauge

I didn't understand some things about $ P/POLY$ class, and I will be thankful if you could help me. as I learned in class, a turing machine M accepts language L with advice $ {a_n} $ if: M(x,$ a_|x| $...