# Questions tagged [complexity-classes]

Computational complexity classes and their relations

674 questions
Filter by
Sorted by
Tagged with
76 views

### Where is $\mathsf{BPP^{NP}}$ in the polynomial hierarchy?

We know that $\mathsf{BPP}$ is in $\mathsf{\Sigma^P_2\cap \Pi^P_2}$ by Sipser-Lautemann, as this proof relativizes we can get $\mathsf{BPP^{NP} \subseteq \Sigma^P_3\cap \Pi^P_3}$, but are there any ...
• 31
60 views

### Is there a complexity class defined as fixed Boolean combinations of problems in $\mathsf{BPP} \cup \mathsf{BH}$?

I have 2 type of decision problems: either in $\mathsf{BPP}$ or in $\mathsf{NP}$; and I want to decide fixed Boolean combinations of them. Since $\mathsf{BPP}$ is closed under Boolean combinations and ...
54 views

### Why can't we just reduce from Bounded HALT to Bounded PCP?

We know that: PCP is famously undecidable (as it can encode any DTM), but Bounded-HALT (DTM on some input halts in at most k steps) is EXPTIME-complete, and Bounded-PCP (there is a matching ...
• 101
142 views

### Is there a 'mathematical program' to separate P from BQP?

This question has been motivated by the existence of an ongoing (and possibly long-term) program for $P\neq NP$ conjecture like GCT(Mulmuley, 1999). Usually, such programs are marked by long and ...
• 225
1 vote
73 views

### Are there any candidate languages in NE but not E?

Let ${\bf E}=\text{DTIME}(2^{O(n)})$ and ${\bf NE} = \text{NTIME}(2^{O(n)})$ Is there any candidate natural language being in ${\bf NE} \setminus {\bf E}$, that is, people believe is ${\bf NE}$ but ...
• 11
134 views

### Solve 3CNF in Poly-Time with Satisfiability Oracle

The problem: Given an algorithm A which can tell whether any 3CNF formula is satisfiable in poly-time, develop an algorithm B that calculates a solution for the formula, also in poly-time, using A as ...
263 views

### What's wrong with this $P \neq BPP$ proof?

I developed this simple argument while learning about the $BP$ operator and McCreight and Meyer's Union Theorem, however I cannot pinpoint where my error is. By the Union Theorem, there exists a total ...
153 views

### Are there any problems in $\mathsf{BPP}$ that are known to be $\mathsf{RP}$-hard or $\mathsf{coRP}$-hard?

It's suspected that probabilistic complexity classes such as $\mathsf{RP}$ or $\mathsf{BPP}$ don't have complete problems. Of course, their promise counterparts have complete problems, but I am not ...
• 355
476 views

### What can we do with a generic oracle (as opposed to a random one)?

Let me first recall a few (lengthy but hopefully mostly standard) facts and definitions in order to motivate my question (feel free to skip down to the actual question): Standard definitions: A ...
• 841
1 vote
74 views

### Crafting ${NP}^{\#P}$-complete problems

Some related posts: Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$? $\mathsf{NP^{PP}}$ vs $\mathsf{P^{PP}}$ I needed a complete problem for the class ${NP}^{\#P}$ for a reduction to show the hardness of some other ...
• 11
108 views

### Assume P != NP, does it imply that one-way functions exist?

I define a function f to be one-way iff for any sufficiently large x computing f(x) bounded ...
• 212
291 views

### Deciding finiteness of regular language is NL-complete?

I've been reading the following Habilitation thesis where the author claims (pg. 29): ... First, deciding whether the language of an NFA is finite is in NL ... I'm having trouble seeing why this ...
418 views

• 205
1 vote
122 views

### Complexity of analytic functions and integrals

There exist polynomial - time computable functions, log - space computable functions, and NC - functions. Given this: To which class do analytic elementary functions, including trigonometric ones, ...
131 views

### Do fast satisfiability algorithms imply fast algorithms for parity SAT?

$\oplus$SAT is the problem of deciding if the number of satisfying assignments to a CNF formula is odd (and is the standard complete problem for the class $\oplus$P, or Parity-P). Suppose we have a ...
• 3,698
1 vote
86 views

### What complexity class is characterized by having PSPACE verifiers?

Inspired by the 2 definitions (theorems) I am aware of, that are as follows. A language L belongs to QMA if there exists a BQP verifier V. A language L belongs to NP if there exists a P verifier V. ...
• 920
298 views

### Is there a well-defined notion of an “R/poly” complexity class?

This would be the complexity class of all problems that are decidable in finite time with a polynomial length advice string that can be arbitrarily hard to compute. But potentially undecidable without ...
• 353
1 vote
165 views

### How "Algebrization" is "A New Barrier in Complexity Theory"?

Being an enthusiast in computational complexity theory, I recently came across with this wonderful work Algebrization: A New Barrier in Complexity Theory. My question is about Theorem 5.3 in it (pp. ...
• 19
361 views

### Structural Complexity Theory References

I'm a PhD student in mathematics (mostly studying algebraic geometry), but I've always been interested in computational complexity theory. As an undergraduate, I completed an independent reading ...
• 113
215 views

### Relationships between Descriptive Complexity and Average Case Complexity

Descriptive complexity gives one a logic or at least a logic to express languages in a complexity class. The PH can be defined as the union of all classes that can be expressed in Second order logic. ...
• 1,261
192 views

### Which 1-player games are EXPTIME-complete? Also, are there any known games that are EXPSPACE-complete?

I noticed a lot of 1-player games have been shown to be NP-Hard, like Pac-Man, The World's Hardest Game, Tetris, etc. For PSPACE-Complete, I noticed that Wikipedia listed these 1-player games: It is ...
• 33
45 views

### Reducing the amount of alternations without exponentially increasing the runtime?

Let $\mathsf{AltTime}(g(n), f(n))$ denote the class of languages that are solvable by an alternating machine using $f(n)$ time and $g(n)$ alternations. Is there anything known about the following ...
• 355
71 views

### Are there any examples of problems in ZPP not yet in P? [duplicate]

Is there a problem of which we can prove that it is in ZPP but we don’t yet know whether it’s in P or not?
• 177
301 views

### Complexity of permanent verification

Consider the problem of permanent verification: $\bullet \$ Given a $n\times n$ matrix $A$ with entries in $\{0,1\}$, and given $k\ge 0$, does $Per(A)=k$? Question: Is it known to be NP-hard? Should ...
• 812
104 views

### How do we show directly coNP is in MIP?

I know one can show that by $\mathsf{coNP}\subseteq\mathsf{NEXP}=\mathsf{MIP}$. But here I would like to start with a $\mathsf{coNP}$-complete problem and show there is a two-prover one-round ...
• 139
1 vote
112 views

### Explanation of Complexity class $S_2^P$?

I am trying to understand the complexity class $S_2^P$ defined as (https://en.wikipedia.org/wiki/S2P_(complexity)). A language L is in $S_2^P$ if there exists a polynomial-time predicate $P$ such that:...
• 468
829 views

### Why is the "balanced vs constant function" problem not a proof that P ≠ BPP?

Recently, I came across the problem of figuring out whether a given binary function $f(x)$ is constant (0 for all values of $x$ or 1 for all values of $x$) or balanced (0 for half of values and 1 for ...
• 119
181 views

### Baker–Gill–Solovay Theorem: why $2^n/10$ steps?

Context I'm teaching an introductory complexity theory course right now and although I work in adjacent areas, I'm not an expert on complexity theory myself, so I'm still in the process of working ...
• 273
228 views

### Complexity class of optimization problems whose fractional relaxation is polynomial-time solvable

It is known that the problem of integer linear programming is NP-hard, but its fractional relaxation can be solved in polynomial time. The concept of fractional relaxation can be applied to any ...
• 2,222
1 vote
173 views

• 2,003
257 views

### Is modular square roots modulo primes in $NC$?

Assume modulus is prime. Is modular square roots then in $NC$? If not then, are there special primes or prime powers or numbers related to these (such as $2^k\pm i$ where $i\in\{-1,0,+1\}$) where it ...
• 12.9k
127 views

77 views

### On the Reductions of Functional complexity Classes

In Chapter 10 of Computational Complexity by Christos Papadimitriou, it is noted that reduction between problems of functional complexity classes are defined as follows: Function problem A reduces to ...
80 views

### Complexity of reachability in fractal mazes with traps

Is reachability in fractal mazes with traps EXPTIME complete? A fractal maze includes one or more copies of itself. For example, see the question Decidability of Fractal Maze or Puzzling ...
• 2,577
174 views

### Computation with cellular automata in practice

It is well known that certain cellular automata (CA) are computationally universal, such as Conway's game of life in 2 dimensions or the rule 110 in 1 dimension. As far as I know, they can emulate ...
• 141