Questions tagged [complexity-classes]

Computational complexity classes and their relations

686 questions
Filter by
Sorted by
Tagged with
71 views

Is this class between BPP and PP?

In analogy to BPP, I define a class XYZ (maybe it already has a name) as follows. For every language $L$ in XYZ, there is an algorithm $M$, such that: $M$ runs in polynomial time on the size of its ...
1 vote
107 views

Graph canonization vs. NP

Is graph canonization (GC) in NP? Is it NP-hard? If unknown, what would be your best guess and why? GC is GI-hard (GI-completeness is unknown), with the graph isomorphism problem being in NP and a ...
• 267
256 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 ...
• 267
36 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,...
1 vote
150 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 ...
• 11
105 views

On the power of QMA(2)

I searched for references. But I could not find any. Is $EXP\subseteq QMA(2)$ known?
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-...
1 vote
130 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 ...
• 245
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)$;...
399 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 ...
193 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 ...
• 247
100 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 ...
• 41
66 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 ...
90 views

1 vote
175 views

Decidability of the complexity of decision problems

This might be a question that is related to some of the existent questions on the topic in the title, but I still find some answers either not full, or the topic still slightly different (maybe due to ...
• 111
131 views

• 13.1k
79 views

Variants of complexity classes that allow "adversarial inputs"?

Wikipedia defines BPP as follows: Alternatively, BPP can be defined using only deterministic Turing machines. A language L is in BPP if and only if there exists a polynomial p and deterministic ...
• 271
121 views

Complexity of computation of ANF-form (Zhegalkin polynomial)

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 ...
• 2,013
162 views

Consequences of $P^{NP[o(n)]} = P^{NP}$

I am wondering what the consequences of $\text{P}^{\text{NP}[o(n)]} = \text{P}^{\text{NP}}$ are. Does this imply the collapse of the polynomial hierarchy or contradict something like $\text{ETH}$? I ...
43 views

Tape reduction, tape compression and time compression

In our lecture we have the following relationships: I have problems to understand these abstract classes. First of all, our Turingmachines are defined as $1$ input tape and $k$ working tapes. DSPACE(...
$\mathsf{coNP}^{\mathsf{\#P}}$ and $\mathsf{coNP}^{\mathsf{\#P}^\mathsf{\#P}}$
I was reading a paper that demonstrates that deciding whether a loop-free program is $\varepsilon$-differentially private is $\mathsf{coNP}^{\mathsf{\#P}}$-complete. What are some other problems that ...