# Questions tagged [complexity-classes]

Questions about relationships between complexity classes.

55 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
137 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 ...
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 ...
145 views

### Have any natural complexity classes been proven not to be closed under complement?

Many important (non-deterministic) complexity classes like NP are believed not to be closed under complement. But have any of them been proven not to be? I'm sure one could construct some contrived ...
101 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 ...
281 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 ...
40 views

### Approximate algorithms for class P problems

As a part of my Algorithm course we studied Approximate Algorithms for NP-complete or NP-hard problems, e.g. "set cover", "vertex cover", "load balancing", etc. My professor asked us as an extra ...
102 views

### What is the consequence of $\oplus P\neq PP$?

From $P\subseteq \oplus P \subseteq PSPACE$ and $P\subseteq PP \subseteq PSPACE$ we infer $\oplus P\neq PP$ gives that $$P\neq PSPACE.$$ Are there any other consequences?
438 views

### Hardness of counting solutions to NP-Complete problems, assuming a type of reduction

The $\text{NP-Complete}$ class of problems is defined w.r.t Karp Reductions, which are polytime many-one reductions. However, they need not necessarily preserve the number of solutions. A more ...
61 views

### Proving a pattern exist in a string without revealing where

Some time ago i read the following problem (i don't remember the article from which i read it from) : "Suppose you are given a picture where the goal is to find waldo (from the game where is waldo), ...
48 views

### Is PSPACE vs NEXPTIME known?

I know that P = PSPACE is a famous open problem, and that EXPTIME = NEXPTIME is also unknown. By the time heirarchy theorem we know that NP is a strict subset of NEXPTIME. Is anything known about ...
27 views

### Do undecidable problems have no HO query? If so, could I have an example?

In descriptive complexity, HO corresponds to ELEMENTARY. ELEMENTARY is a subset of R, so therefore all HO queries are decidable. Then undecidable problems have no corresponding HO query. Is my ...
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 ...
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$?
43 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?
195 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, ...
55 views

### Status of $BQP^{NP},NP^{BQP}$

The relation between $BQP$ and $NP$ is an open problem, while it seems that $BQP$ is somewhat lower for $NP$ than the other way round. Is the status of lowness of these problems known?
35 views

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 ...
120 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 ...
217 views

### Misunderstanding the Baker-Gill-Solovay oracle and obtaining $LOGSPACE^A=PSPACE^A$

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 \...
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? ...
175 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 ...
45 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 ...
37 views

### What is at least weakly NP-hard problem?

It is known that some problem P is at least weakly NP-hard. What does at least part of the statement mean? Is it possible that problem P is strongly NP-hard? Is this a stronger, i.e. more precise, ...
16 views

### Prove that a set is decidable using time constructible function

I'm preparing an exam of theory of computation and I'm very in trouble with some exercise. Considering a Turing machine $\mu$ of alphabet $A=\{ 0,1 \}$ (we don't know nothing about termination) and a ...
21 views

### Proof by padding: $\textsf{TIME}(t_1(n)) = \textsf{TIME}(t_2(n)) \implies \textsf{TIME}(t_1(f(n))) = \textsf{TIME}(t_2(f(n)))$

I've been given the task of proving the statement in the title, which I found out it should be called the translational lemma by means of a padding argument; $f$, $t_1$ and $t_2$ are three ...
31 views

### A heuristic for finding an edge cycle cover

I am looking to find a minimum list of cycles in a graph such that their union gives the list of all simple cycles in this graph. In the example below, here are 4 simple undirected cycles: 1-2-3, 2-3-...
29 views

### Cook Levin Theorem (Sipser Proof) (phi move)

In Sipser's proof of the cook levin Theorem the move function (phi move) checks whether a given window is legal. For that we must have an exhaustive set of all possible legal windows to verify that a ...
35 views

### Why is $DSPACE(\log(n)) = NSPACE(\log(n))$ not known?

Here $DSPACE(\log(n))$ is the family of algorithms for which there exists a deterministic Turing machine using $O(\log(n))$ space. On the other hand $NSPACE(\log(n))$ is the family of algorithms for ...
84 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 ...
19 views

### $P$ with $SAT[k]$ and $NP[k]$ oracles?

We know $coNP$ is in $P^{NP}$ and so does $coNP$ in $P^{NP}$ and $P^{SAT}$ hold? Is there a difference between $P^{SAT[k]}$ and $P^{NP[k]}$ at any $k\geq0$?
45 views

### Intersection of decision problems?

Say we have two problems $\Pi_1\in NP$ and $\Pi_2\in coNP$. Where does $\Pi_1\cap\Pi_2$ live?
18 views

### Why is $BPP^{NP}$ in the polynomial hierarchy?

Why is $BPP^{NP}$ in the polynomial hierarchy? I know that $BPP$ is contained in $NP^{NP}$, so $BPP$ is inside $PH$. Should I just simply reuse the proof of $BPP\subset NP^{NP}$, feed in each machine ...
44 views

### Reduction of complement from complexity class co-np and p

Let P $\neq$ NP. D is in the complexity class co-NP. B is in the complexity class P. Let $\bar{D}$ be the complement of D, then $\bar{D}$ $\leq _ {p}$ B. Is this statement true or false? My ...
40 views

### $\mathbb{NEXP\subseteq(NEXP\cap coNEXP)/poly}\implies \mathbb{NEXP=NEXP\cap coNEXP}$

We already know that $NEXP\subseteq EXP/poly\implies NEXP=EXP$. What if we change $EXP$ to $NEXP\cap coNEXP$. As the title states, prove the statement in the title. The original proof use the self-...
314 views

### Modular exponentiation running time

I read on Wikipedia that modular exponentiation can be done in polynomial time. I've a few questions regarding it (sorry if they seem a bit easy – I'm not a comp sci student). Is it poly ...
57 views

### Decidability of language that contains all TM encodings that accept at least one word

I have a language that contains all encodings of the Turing machines that accept at least one word. Is this language recursive, recursively enumerable, or neither?
62 views

### A clarification on $NP=coNP$?

If we have two $NP$ complete problems $\Pi_1$ and $\Pi_2$ such that yes instances of $\Pi_1$ are no instances of $\Pi_2$ and vice versa then we know $NP=coNP$. Is the converse true as well? ...
25 views

### Clarification on a theorem?

The proof of theorem 27 in http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IKW02/IKW02.pdf suggests 'If $NEXP = MA$, then $NEXP ⊂ P/poly$". However looking at it seems it is close to stronger '...
95 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 ...
Suppose we have a complexity class $C$ (say for example $C = DTIME(2^{cn})$). Take a language that belongs to $C$: $L \in C$. Define an arbitrary polynomial reduction from language $L$ to $L'$. To ...
Wiki gives two definitions for the NEXP complexity class: $\mathsf{NEXPTIME} = \bigcup_{k\in\mathbb{N}} \mathsf{NTIME}(2^{n^k})$ where $\mathsf{NTIME}(f(n))$ is the set of decision problems that ...