Questions tagged [complexity-classes]

Questions about relationships between complexity classes.

Filter by
Sorted by
Tagged with
8
votes
1answer
197 views

is $P_{CTC} = BPP_{path}$?

I think that these two classes should be the same, but I can't find any literature about this and have a limited background on the topic. This is my reasoning, and I would like to know if (1) this is ...
3
votes
1answer
108 views

Differences between $\text{BPP}$ and $\overline{\text{BPP}}$ vs $\text{co-BPP}$

Is $\overline{\text{BPP}}$ different from $\text{co-BPP}$? I am having trouble understanding the "co" part of these complexities. I think yes and here is what I think: It seems given that $\text{BPP}$...
1
vote
1answer
566 views

If NP is the class of problems that cannot be solved in polynomial time, what is co-NP?

In my super non-rigorous class on optimization, the prof defined NP as the class of decision problems that cannot be solved in polynomial time. By definition, P is the class of decision problems that ...
7
votes
1answer
222 views

$\mathsf{PP=RP}$ consequences

We know $$\mathsf{PP=RP},\mathsf{coPP=coRP},\mathsf{PP=coPP=coRP=RP=ZPP=BPP\subseteq P/poly}$$ are equivalent and the polynomial hierarchy collapses to $2$nd level. What are the other non-trivial ...
5
votes
1answer
802 views

If NP is not a proper subset of coNP, why does NP not equal coNP?

I am studying some lecture notes on the complexity of algorithms. The notes give a proof that NP is not a proper subset of coNP. However, they still assert that NP is a subset of coNP (which I agree ...
6
votes
1answer
658 views

Notation: SPACE(n) vs SPACE(O(n))

I want to denote the class of problems solvable by linear space multi-tape Turing machines. I have seem in many places this class being denoted by $SPACE(n)$. But why is the notation $SPACE(O(n))$ not ...
1
vote
1answer
184 views

On SUBEXP ⊆ P/poly

According to answers here Are there subexponential-time algorithms for NP-complete problems? $\mathsf{NP}$ complete problems can be in $DTIME[2^{n^{1/\alpha}}]$ for $\alpha>1$. Now supposing $...
1
vote
0answers
130 views

FPTAS, except not polynomial in size: which class?

Problems in FPTAS require time which is (at most) polynomial in problem size. Suppose this last requirement is relaxed. What is the corresponding approximability class and where can one read about it? ...
-1
votes
1answer
104 views

Prove that we can change probability in definition of PP class

According to Wikipedia, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. If the answer ...
15
votes
1answer
313 views

Complexity classes pertaining to listing all solutions?

I was reading a question over at Stack Overflow asking whether it was NP-hard to list all simple cycles in a graph containing a particular node and it occurred to me that I couldn't think of any ...
1
vote
1answer
486 views

Proving complexity by reduction using strongly NP-hard problem

I have a decision problem $X$ of which I think I can show its complexity by using a reduction from a problem $Y$ that has been shown to be strongly NP-hard. I tried to follow the same procedure as ...
2
votes
1answer
83 views

Relationship between PP and PH

Toda's theorem says that $PH \subset P^{PP}$. Does this imply any relationship between $PH$ and $PP$ that does not involve oracles? Does it imply either that $PH \subset PP$ or that $PP \subset PH$? ...
3
votes
1answer
552 views

Does NP = coNP imply the collapse of PH to level 1?

It was already asked here whether NP=coNP implies P=NP. I'd like to approach that question from the perspective of the Polynomial-Time Hierarchy. Here is a theorem from Oded Goldreich's "...
4
votes
1answer
477 views

Prove that PP is closed under complement

I found this proof in Wikipedia, but one of the most important steps in it doesn't make any sense to me. I'll explain: By the definition of PP there is a polynomial-time probabilistic algorithm ...
3
votes
3answers
1k views

What is the relation between EXPTIME and NP HARD complexity classes?

Need to know the relation between EXPTIME and NP HARD complexity classes.
11
votes
1answer
867 views

Collection of APX-hard problems

Everyone knows "Garey & Johnson", which is my go-to reference whenever I need a problem to transform from for an NP-hardness proof. However I recently find myself in need of an APX-hardness proof, ...
4
votes
1answer
733 views

Why is PH in PSPACE?

$PH \subseteq PSPACE$. In order to prove it, one has to show that for a language $A \in \Sigma_k$ (for some $k \in \mathbb{N}$) there exists a turing machine $M_A$ that decides it in polynomial space....
2
votes
1answer
34 views

L contains the concatenations of all k-bit long strings. Why is it decided in PSPACE(loglogn)?

(This exercise is from Computation Complexity: A Conceptual Perspective by Oded Goldreich): For any k $\in \mathbb{N}$, let $w_k$ denote the concatenation of all k-bit long strings (in lexicographic ...
5
votes
1answer
123 views

Why does P/Poly can also receive bad advice?

(from my class's slides) "NP and P/Poly both use an external string for computation. However, for L in NP, any witness is rejected if x $\notin$ L. For L in P/Poly, there can be bad advice!" I'm ...
3
votes
1answer
42 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
23 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 ...
2
votes
1answer
95 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
514 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 ...
1
vote
0answers
118 views

Proving that $BPP^{BPP}=BPP$ [duplicate]

I'm trying to prove that $BPP^{BPP}=BPP$. $BPP\subseteq BPP^{BPP}$ is obvious. I'm struggling with $BPP^{BPP}\subseteq BPP$.. Can anyone help?
6
votes
1answer
616 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
374 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}$...
4
votes
1answer
317 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
89 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
1answer
169 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: $...
3
votes
0answers
86 views

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

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?
11
votes
1answer
4k 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 ...
2
votes
1answer
61 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
210 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 ...
1
vote
1answer
870 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
98 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 ...
4
votes
1answer
80 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 ...
8
votes
3answers
538 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
196 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}...
7
votes
1answer
296 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
41 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
88 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
99 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
277 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
92 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: ...
13
votes
2answers
8k views

PTAS definition vs. FPTAS

From what I read in the ...
2
votes
0answers
42 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
2k 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
84 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
111 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
870 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.

1 2 3 4 5 7