# Questions tagged [complexity-classes]

Questions about relationships between complexity classes.

76 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
142 views

### Complexity class for probabilistic approximation algorithms with bounded error

What's the name of a complexity class of optimization problems that have "bounded error probabilistic approximation algorithms"? Bounded error probabilistic version of APX (as BPP is bounded error ...
346 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 ...
129 views

### Is there a polynomial-time algorithm to minimize regular expressions without Kleene closures/stars?

I have read that minimizing regular expressions is, in general, PSPACE-complete. Is it known whether minimizing regular expressions without the Kleene closure (star, asterisk) is in P? The language ...
32 views

### What is a term for a problem that is hard to approximate within a factor $c$?

Let $f$ be a maximization problem. If there is a reduction from SAT to the following problem: "given an integer $c$, decide if there is an $x$ for which $f(x)\geq c$", then $f$ is NP-hard. ...
324 views

### PARITY using depth one TC0 circuit

I need to disprove that a PARITY gate can be simulated using a single MAJORITY gate, or even a ...
46 views

### Sufficient condition for a complexity class's closure under NP-reductions?

Let us say that there exists a $\mathsf{NP}$-reduction from a problem $A$ to another problem $B$ when there exists a non-deterministic, polynomial-time Turing machine $T$ such that for each $a \in A$, ...
75 views

13 views

### $W$-hierarchy and parameterized search problems

I have two related questions: What are the ways to prove that a certain problem is in $W[t]$ in the W-hierarchy for parametrized complexity, except using the straight definition of boolean circuits? ...
34 views

### Consequence of NP-complete, and DP-complete w.r.t. randomized reductions

If a problem is NP-complete with respect to randomized (polynomial time) reductions, but not with respect to deterministic reductions, then we have P $\neq$ BPP (See Question 2 here and its answer). ...
34 views

68 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 ...
145 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 ...
231 views

Baker, Gill and Solovay  gave an oracle $A$ relative to which $P^A=PSPACE^A$. The oracle is the very simple $PSPACE^A$-Complete language $$A = \{\langle M, x, 1^n \rangle | M^A \text{ accepts } x \... 0answers 137 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? ... 0answers 183 views ### Proving CVal is RP-hard Let CVal be the language of all <C,s> where s is an n-tuple of binary values (\{0,1\}), such that C is a variable-free boolean circuit (gates \wedge, \vee, \neg, 0, 1), and ... 0answers 47 views ### Canadian traveller problem on directed acyclic graphs What is the complexity of the Canadian traveller problem variant where the only thing that is seen is a single node ahead on a directed acyclic graph so that we cant go back once we go to a new node ... 1answer 147 views ### Proving that NPSPACE\subseteq PSPACE using the proof of Savitch's Theorem We were shown a proof of NPSPACE\subseteq PSPACE in class. In short, the proof says: Let L\in NPSPACE. Then there exists a non-deterministic polynomial space bounded Turing machine M that ... 0answers 19 views ### What is the depth of comparator circuit required in Gale Shapely and STCONN? Stable matching problem and STCONN can be solved using comparator circuits (refer https://arxiv.org/abs/1208.2721). What is the depth of the CC circuit necessary for stable matching? Is it in CC^... 0answers 49 views ### A paper claiming that optimization version of symmetric TSP can be solved in polynomial time In the following paper : Czopik, J. (2019) An Application of the Hungarian Algorithm to Solve Traveling Salesman Problem. American Journal of Computational Mathematics,9, 61-67. In the Introduction, ... 0answers 39 views ### Is this combinatorial seach problem NP-complete? The context: Consider the following optimization problem. Let f_1,\dots,f_L:\mathbb{R}\to\mathbb{R} arbitrary (continous) functions for L>1 and x_k\in\mathbb{R} evolve according to$$ x_{k+1}...
Consider two statements. Statement 1: The problem #3SAT (finding the number of satisfying instances to a 3SAT problem) is #P-hard. Statement 2: Additively approximating #3SAT upto $\pm 2^{n/2}$ error ...