Questions about relationships between complexity classes.

learn more… | top users | synonyms

0
votes
0answers
9 views

IS $L=QMA$ an open problem?

Having read several 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
45 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
595 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
38 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
0answers
14 views

How do we know that xTIME is a subset of xSPACE?

I'm just starting with Complexity and I can't figure out why do we say that xTIME is a subset of xSPACE (for x in ...
-1
votes
1answer
48 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
41 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
44 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
19 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
231 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
118 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 ...
5
votes
1answer
237 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
35 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
34 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
51 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
70 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 ...
-1
votes
2answers
40 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
268 views
1
vote
0answers
24 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
77 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
67 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
30 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
47 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
94 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
32 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
65 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
95 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
67 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
116 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
79 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
36 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
79 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
46 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
109 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
103 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
47 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
94 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
161 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
87 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 ...
2
votes
0answers
62 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
310 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
54 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
52 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| ...
5
votes
1answer
76 views

Is L closed under linear-time reductions?

L is as usual the complexity class DSPACE($\log n$), of languages decidable using a deterministic Turing machine using logarithmic workspace. Is L closed under linear-time reductions? It is ...
1
vote
0answers
62 views

Suppose P = NC - what then? [duplicate]

Suppose tomorrow someone discovered a proof that P = NC. What would the consequences for computer science research and practical applications be in this case?
0
votes
0answers
29 views

NP-Hard vs NP-Complete Why NP-complete so important? [duplicate]

A problem $L$ is NP-complete when:- $L\in \text{NP}$ For every problem $L' \in \text{NP}$, $L'$ is polynomial time reducible to $L$ When at least property 2 is satisfied for a problem $L$ (but ...
3
votes
2answers
144 views

What is practical difference between NP and PSPACE-complete?

Here's something that has puzzled me lately, and perhaps someone can explain what I'm missing. Problems in NP are those that can be solved on a NDTM in polynomial time. Now assuming P$\,\neq\,$NP, ...
1
vote
1answer
86 views

Prove that $S_2$ is closed under union and complement

I'm having trouble proving that $S_2$ is closed under union and complement, even though in this Wikipedia article it says that: It is immediate from the definition that $S_2$ is closed under union ...
9
votes
0answers
68 views

Are there any known AM-complete problems/is AM-complete well defined?

I'm curious about whether there are any complete problems in the Arthur-Merlin complexity class. Graph Non-Isomorphism (GNI) seems to be the canonical example of a problem in AM, but it's probably not ...
3
votes
2answers
159 views

How can P=NP relate to creativity and proof automation, as said by Scott Aaronson?

I read several times of Scott Aaronson saying that P=NP implies that human creativity is boring and something like that, and that P=NP has something to do with proof automation. I don't get his ...