Questions tagged [complexity-classes]

Questions about relationships between complexity classes.

49 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
10
votes
0answers
135 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 ...
8
votes
1answer
190 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 ...
5
votes
0answers
95 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 ...
5
votes
1answer
125 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 ...
4
votes
0answers
255 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 ...
3
votes
0answers
31 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 ...
3
votes
0answers
432 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 ...
2
votes
0answers
39 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 ...
2
votes
0answers
26 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 ...
2
votes
1answer
99 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?
2
votes
0answers
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 ...
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
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
0answers
189 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, ...
2
votes
0answers
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?
2
votes
0answers
35 views

crypto protocols from complexity class

Assume $P=PSPACE$. Then would it be possible to design cryptographic protocols based that is easy to compute from $PSPACE$ but hard to invert from something higher up in hierarchy? A function $f: \{0,...
1
vote
0answers
19 views

Which is harder, an NP-complete problem or the Raz-Tal oracle problem?

This is a (hopefully) sharper version of a question that I asked previously. Which of these algorithms is believed to have a longer asymptotic runtime? The optimal algorithm guaranteed to solve some ...
1
vote
0answers
14 views

Do relativized relations between complexity classes tell us anything about the nonrelativized relation?

The existence of relativized relations between complexity classes seems to often be treated as "circumstantial" evidence about the "true" or "real-world" (i.e. nonrelativized) relation between the ...
1
vote
0answers
8 views

$NC$ and $FNC$ oracles low for functional and Stockemeyer classes respectively?

We know $P^{NC}=P$ and $FP^{FNC}=FP$ hold. Do $FP^{NC}=FP$ and $P^{FNC}=P$ hold?
1
vote
0answers
16 views

Other problems in UP and co-UP

Are there any known problems in $UP \cap co-UP$ other than integer factorization and parity games (or a problem that can be reduced in polynomial time to either problem), that aren't known to be in $P$...
1
vote
0answers
27 views

What if $PSPACE$ falls to non-uniformity?

We know if every language in $EXP$ has polysize circuits, then $P\neq NP$ and $EXP=PSPACE=\Sigma_2^P\cap\Pi_2^P$. If every language in $PSPACE$ has polysize circuits, then does it give anything (note ...
1
vote
0answers
50 views

Is it suspected that $DTIME(o(f(n)))\subsetneq DTIME(f(n))$?

Time hierarchy theorem states that $DTIME\bigg(o\Big(\frac{f(n)}{\log n}\Big)\bigg)\subsetneq DTIME\big(f(n)\big)$. However space hierarchy theorem is stricter in that point since it states $SPACE\...
1
vote
0answers
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 ...
1
vote
0answers
115 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 ...
1
vote
0answers
204 views

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

Baker, Gill and Solovay [1] 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 \...
1
vote
0answers
128 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
vote
0answers
173 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 ...
1
vote
0answers
43 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 ...
0
votes
0answers
29 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-...
0
votes
0answers
25 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 ...
0
votes
0answers
31 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 ...
0
votes
1answer
59 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 ...
0
votes
0answers
17 views

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

We know $coNP$ is in $P^{NP}$ and so does $coNP$ in $P^{NP[1]}$ and $P^{SAT[1]}$ hold? Is there a difference between $P^{SAT[k]}$ and $P^{NP[k]}$ at any $k\geq0$?
0
votes
0answers
43 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?
0
votes
0answers
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 ...
0
votes
0answers
38 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 ...
0
votes
0answers
37 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-...
0
votes
1answer
227 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 ...
0
votes
0answers
55 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?
0
votes
0answers
60 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? ...
0
votes
0answers
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 '...
0
votes
0answers
87 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 ...
0
votes
0answers
55 views

How does a given complexity class change under polynomial reduction?

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 ...
0
votes
0answers
65 views

Equivalence between the two definitions of NEXPTIME complexity class

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 ...
0
votes
0answers
90 views

2-depth arithmetic circuits and VP vs VNP

the field of arithmetic circuit complexity is undergoing major discoveries in recent years as mentioned by Fortnow. am looking for a more layman-readable summary: is this new paper Sums of ...
-1
votes
1answer
50 views

A simple clarification on polynomial hierarchy

$P^{NP}\subseteq BPP^{NP}$ holds. According to current knowledge $BPP$ is in $\Sigma_2^P\cap\Pi_2^P$ holds. So according to current knowledge is following true? $P^{\Sigma_2^P\cup\Pi_2^P}\subseteq ...
-1
votes
1answer
30 views

Complexity classes that are low for equivalent definitions of $\mathrm{PP}$

What is the biggest complexity class that is low for each other equivalent definition of $\mathrm{PP}$? I already know that $\mathrm{PP}^\mathrm{BQP}=\mathrm{PP}$. This is a lowness result using ...
-1
votes
1answer
193 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$ ...
-1
votes
1answer
101 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 ...