# Questions tagged [complexity-classes]

Computational complexity classes and their relations

684 questions
Filter by
Sorted by
Tagged with
21 views

### Integration of analytic function

It is the continuation of the question: Complexity of analytic functions and integrals. Given an input integer $t$ and a sequence of analytic functions $f_n(\cdots(f_0(x))$, with parameters $t$ itself,...
132 views

### Complexity of finding graph automorphism group vs. canonization

Given a generating set for the automorphism group of a graph, can we efficiently find a canonical labeling? What about the other way around? Both problems of finding a graph automorphism group and ...
4k views

### What would be the consequences of $\mathsf{PH=PSPACE}$?

A recent question (see Consequences of NP=PSPACE) asked for the "nasty" consequences of $\mathsf{NP=PSPACE}$. The answers list quite a few collapse consequences, including $\mathsf{NP=coNP}$...
1 vote
145 views

### Use of transitive closure in proof of NC hierarchy collapse

Im looking at the proof of $NC^{i} = NC^{i+1} \implies NC = NC^i,\,i\geq 1$ in page 10 of the following article: https://www.cs.uoregon.edu/Reports/TR-1986-001.pdf I understand the general idea ...
113 views

### Are there NPO (NP Optimization) problems that would require more than polynomial time even on a non-deterministic machine?

Consider an $\mathit{NPO}$ problem $O = (X,L,f,\mathit{opt})$ according to the definition of $\mathit{NPO}$ found in this answer. What I don't fully understand is what happens if we use a NDTM (non-...
103 views

### On the power of QMA(2)

I searched for references. But I could not find any. Is $EXP\subseteq QMA(2)$ known?
1 vote
127 views

### Where does a problem lie which is NP-hard but not QMA-hard?

I saw this complexity classes diagram in this quantum computing paper in NATURE. Based on the standard assumption of $P\neq NP\neq QMA$, they also seem to have related the NP-hard and QMA-hard ...
126 views

### Is the protocol perfect zero knowledge?

Consider such protocol for $GI$ (Graph-isomorphism problem). $P$ randomly chooses permutations $\sigma_1, \sigma_2, ..., \sigma_k$ and sends $H_1 = \sigma_1(G_0), ..., H_k = \sigma_n(G_0)\ (k > 1)$;...
871 views

### Is Parity-P contained in PP?

This question was asked by Jan Pax on the Foundations of Mathematics mailing list. Certainly $P^{\oplus P} \subseteq P^{\#P} = P^{PP}$ but I suspect from the answers to this question that it's not ...
394 views

### Problems where "maximal" is hard, but "maximum" is easy?

For a lot of problems, it's easy to find a maximal solution (say, with a greedy algorithm), but that will in general not be maximum, and in fact computing a maximum solution might be computationally ...
192 views

### What is the probability a random language in $\mathsf{PSPACE}$ is in $\mathsf{P}$?

Suppose I am drawing a venn diagram of complexity classes, and I don't want one that is the most visually pleasing, but the most accurate. How much of PSPACE should P take up? Let $L$ be chosen ...
98 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 ...
1 vote
177 views

58 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 ...
158 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 ...
1 vote
79 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 ...
137 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 ...
160 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 ...
269 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 ...
490 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 ...
87 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 ...
112 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 ...
315 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 ...
427 views

1 vote
136 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, ...
135 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 ...
428 views

### Ruzzo-Simon-Tompa oracle access mechanism

In a paper on relativizing logspace computations, Ladner and Lynch construct an oracle relative to which $\mathsf{NL} \nsubseteq \mathsf{P}$. There are some more pathological examples in this vein in ...
847 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 ...
1 vote
88 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. ...
301 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 ...
402 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 ...
1 vote
208 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. ...
225 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. ...
224 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 ...
47 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 ...
265 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 ...
73 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?
307 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 ...
512 views

### Complexity results for Lower-Elementary Recursive Functions?

Intrigued by Chris Pressey's interesting question on elementary-recursive functions, I was exploring more and unable to find an answer to this question on the web. The elementary recursive functions ...
107 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 ...
1 vote
133 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:...
209 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 ...
1k views

### Optimization problems with minimax characterization, but no polynomial-time algorithm

Consider optimization problems of the following form. Let $f(x)$ be a polynomial-time computable function that maps a string $x$ into a rational number. The optimization problem is this: what is the ...
238 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 ...
Let $f: \mathbb{F}_2^n \to \mathbb{F}_2$ be a boolean function. Consider $f$ as a multilinear polynomial over $\mathbb{F}_2$ (algebraic normal form or Zhegalkin polynomial). How hard is to define the ...