# Questions tagged [complexity-classes]

Questions about relationships between complexity classes.

344 questions
Filter by
Sorted by
Tagged with
103 views

### $ACC^{0}$ vs Poly-size circuits of bounded degree

We know that NEXP $\not\subset ACC^0$ (Ryan Williams'10 Result). Also, We know that even $\Sigma_{2}^{P}$ cannot have polynomial circuits of bounded degree i.e. $SIZE(n^k)$ for some $k \in N$ (Kannan'...
111 views

### Clarification on class $SPP$?

A language $L$ is in $SPP$ if there is a $GapP$ function $f$ such that $x\in L\implies f(x)=1$ and $x\not\in L\implies f(x)=0$. By $x\not\in L$ I think we mean $x\not\in SPP$ correct? I would have ...
206 views

### Complexity Classes UP and US

According to complexity zoo: Class UP (Unambiguous Polynomial-Time) is defined as: The class of decision problems solvable by an NP machine such that If the answer is “yes,” exactly one computation ...
134 views

### Low for EXP and NEXP

What are the largest classes which are low for EXP and NEXP? For example: I am aware the class P, QP are low for EXP as well as NEXP. We also know that NP is not low for either of them. Is class ...
64 views

### On lowness of $\oplus P$

$\oplus P$ is low for itself ($\oplus P^{\oplus P}=\oplus P$). Are there other complexity classes $\mathcal D$ that satisfy $\mathcal D^{\oplus P}=\oplus P$? Are there complexity classes $\mathcal C$ ...
25 views

### Some questions about the depth hierarchy of threshold circuits

Let me split my query into a few parts which possibly have overlapping answers, How do we prove that depth $3$ threshold circuits with polynomially bounded integral weights (call this $\hat{LT_3}$) ...
305 views

459 views

### Is NPSPACE also closed under polynomial-time reduction and under log-space reduction?

The complexity classes P, NP, and PSPACE are closed under polynomial-time reduction. The complexity classes L, NL, P, NP and PSPACE are closed under log-space reduction. I wonder if NPSPACE is also ...
2k views

### A problem is NP-hard iff its complement is coNP-complete

$A$ is NP-hard iff $\overline{A}$ is $coNP$-hard, where $\overline{A}$ does mean complement of $A$. I can't figure out why it is true. Let $A\in NP-hard$. I know that each problem in $NP$ is ...
51 views

102 views

### Confusing method of proving PSPACE-completness

I don't understand a way of proving PSPACE-completness. The way was used by my lecturer. I can use reduction, however following method confuse me: We consider sequence (of polynomial length) of ...
112 views

### Asserting Run Time From Big O Function

Related to this, but I felt it was more appropriate to ask as a separate question: The complexity of Shor's algorithm is of order $$O\left(n^2\,\log(n)\,\log(\log(n))\right)$$ with $n$ the bit ...
246 views

### Never Brute Force?

Does there exist a more optimum algorithm to solve every problem than brute force (or an equivalent)? A brute force algorithm for the purpose of this question is defined as an algorithm of time ...
93 views

### Is there some problem in “promise-DSPACE(o(log log n))” that is also in “promise-DFA”?

Disclaimer I have no idea about complexity theory. If this question makes no sense or is wrong, mods are free to delete the question I´ve read somewhere that the problems that can be correctly ...
204 views

### Query regarding PP complexity class vs NP?

Considering the complexity classes $NP$, $co-NP$ and $PP$: $NP$ and $co-NP$ are both contained in $PP$. For any Language $L$ suppose we have the mechanism that: If the oracle of $co-NP$ implies $No$ ...
115 views

### Demonstration that EXP is closed under union complementation and concatenation

How can I demonstrate that the EXP class is closed under union, concatenation, and complementation?
453 views

### Is this graph problem NP-hard / NP-complete?

I have a certain kind of graphs. They are DAGs similar to dependency graphs but strictly hierarchical, that is, each node belong to a certain level in the hierarchy and cannot be moved up or down when ...
556 views

### What does the complexity class $\mathsf{XP}$ stand for?

$\mathsf{XP}$ is the class of problems with input length $n$ and parameter $k$ than can be solved in $O(n^{f(k)})$ time, where $f$ is a computable function. It's described on the complexity zoo page ...
67 views

### On oracle access containment?

If $X,Y$ are complexity classes in the polynomial hierarchy with $X\subseteq Y$. With abuse of notation assume $X,Y$ also as the TMs that accept languages in classes $X,Y$ respectively. Then is it ...
119 views

### prove that $BPP(\alpha(n), \beta(n)) = BPP$

prove that for every $0 \le \alpha(n), \beta(n) \le1 \; s.t.$ there exists $c \in \Bbb{N} \;s.t \;\alpha(n)+\beta(n) \le 1- \frac{1}{n^c}$ then $BPP(\alpha(n), \beta(n)) = BPP$. I tried to show that ...
119 views

### Prove that $NP^{NP\cap co-NP} = NP$

Let $A\in NP\cap co-NP$. Then, $NP^A = NP$. At first, I thought: Easy, let $L\in NP^A$ s.t. $A\in NP\cap co-NP$. Let $M_L$, an $NDTM$ to decide $L$ and $M_A$, an $NDTM$ to decide $A$. Then, we could ...
179 views

### Space-unconstructable function in the proof of Savitch's theorem

I'm learning about the Savitch's theorem, and while the construction proof is straightforward, I still don't understand one part about it. The proof I'm talking about is the same as is currently on ...
272 views

### Non-deterministic logarithmic time complexity class

Is that true that $Time(O(log(n)))=NTime(O(log(n)))$ iff $P=NP$? It seems to me to be true, as I only need to take log on both sides, since log of a polynomial is $O(\log(n))$, but I don't know how to ...
203 views

### Showing a problem is in coNP

We have the problem $C = \{<G,S>| \text{ S is a minimal cover of G }\}$ and we want to show that $C\in coNP$. I can easily show that there's a ND TM that decides $coC$ using a guess to check if ...
99 views

### What does $L$-uniformity mean?

I've understood that $L$-uniformity means that there's a TM that can output the description of $C_n$ in $O(\log n)$ space. Now, that seems odd to me since the description itself (as far as I ...
123 views

### Why 0-BPP equals P

Sorry if it is an obvious question, since all my searches lead to "clearly 0-BPP=P" (like Papadimitriou text book or Complexity Zoo). I understand that any P machine can be seen as a 0-BPP machine ...
224 views

### Decision problems whose verifier is NP

We define $\mathbf P$ as the set of problems solvable in polynomial time. We define $\mathbf{NP}$ as the set of problems with a verifier $\in \mathbf P$. Is there a name for problems whose verifiers ...
162 views

### Is P the set of all algorithms whose run-time is $O\left( n^{ O \left( 1 \right) }\right)$?

I'm coming to Computer Science from Mathematics and am familiar with the idea of building classes of objects using Propositional Logic. Namely, start with some universe of objects, define some ...
8k views

### Would the P vs. NP problem become trivial as a result of the development of universal quantum computers?

If someone were to build a universal quantum computer, would that have any implications on the problem of P vs. NP?
192 views

### Precise definition of oracle classes $A^B$

I was reading in Papadimitriou's "Computational Complexity" book Chapter 14, about Oracle Machines. Papadimitriou defines, in definition 14.3, page 339-340, Oracle Turing Machines with oracle a ...
55 views

### A query on $\#P$ and $NP$?

We know that if a $\#P$-complete problem has a deterministic reduction to $FNP$ version of an $NP$-complete problem then polynomial hierarchy collapsed to first level. Is there a consequence if we ...
209 views

1k views

### Decision version of the traveling salesman problem and NP-hardness

Wikipedia says: The problem has been shown to be NP-hard and the decision problem version ("given the costs and a number x, decide whether there is a round-trip route cheaper than x") is NP-...
537 views

### Precise relation between complexity classes(focus on P, NP and EXPTIME)

I am interested in the precise relation between $P$, $NP$ and $EXPTIME$ classes. What I know so far: $P \subseteq EXP$ (from Time Hierarchy Theorem [1]) We don't know an exact relation between $P$ ...
553 views

### How to use succinct circuits to construct an EXPTIME complete problem?

When reasoning with NP-completeness, I find SAT and k-clique more convenient to reason with than generalized games that are NP-complete or the Turing machine model. I'm looking for something similar ...