<we><edit> <!-- questions and answers -->
derandomization
conditional-results
linear-programming
lg.learning
cg.comp-geom
clique
graph-isomorphism
big-picture
graph-algorithms
lambda-calculus
gt.game-theory
graph-theory
coding-theory
it.information-theory
advice-request
automata-theory
quantum-computing
cr.crypto-security
randomized-algorithms
convex-optimization
ct.category-theory
time-complexity
approximation-hardness
reference-request
ai.artificial-intel
complexity-classes
PromiseBQP and expectation values of operators
complexity-classes
quantum-computing
promise-problems
Why are circuit classes AC0, ACC0, etc. unavoidable?
cc.complexity-theory
complexity-classes
circuit-complexity
Efficiently computable by a "simple" algorithm?
cc.complexity-theory
complexity-classes
circuit-complexity
What are semantic classes that have a syntactic equivalent?
cc.complexity-theory
complexity-classes
big-list
Benefits for syntactic and semantic classes
cc.complexity-theory
complexity-classes
big-picture
What are the problems in EXPSPACE \ {NEXP ∪ co-NEXP}?
cc.complexity-theory
complexity-classes
polynomial-hierarchy
Reduction from SAT to binary matrix subset problem
cc.complexity-theory
complexity-classes
time-complexity
sat
boolean-matrix
Find a pair of nodes with maximum sum of distances in k given trees
ds.algorithms
graph-algorithms
complexity-classes
tree
parameterized-complexity
If only pathological cases of NP-hard problems are difficult to solve, then why isn't NP-hard defined to only include those pathological cases?
cc.complexity-theory
np-hardness
complexity-classes
soft-question
Complexity of testing if two sets of $m$ points in $\mathbb{R}^n$ differ only by rotation?
cc.complexity-theory
complexity-classes
graph-isomorphism
computational-geometry
high-dimensional-geometry
Printing all paths of a tree and sorting the weight of edges
graph-theory
graph-algorithms
complexity-classes
ds.data-structures
NEXP-complete problems
cc.complexity-theory
complexity-classes
big-list
nexp
Complexity of modal logic IK5
cc.complexity-theory
complexity-classes
lo.logic
modal-logic
Kolmogorov generic oracle
cc.complexity-theory
complexity-classes
oracles
Using idea of entropy (maybe Shannon entropy or other continuous entropy) to the topic of functional analysis
cc.complexity-theory
complexity-classes
it.information-theory
na.numerical-analysis
shannon-entropy
Does the NP-hardness of finding any valid solution imply NPO-hardness?
complexity-classes
approximation-hardness
approximation
Should GCT focus on $PSPACE\not\subseteq P/poly$?
cc.complexity-theory
complexity-classes
circuit-complexity
lower-bounds
gct
What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?
cc.complexity-theory
complexity-classes
conditional-results
structural-complexity
On sparse complete sets and P vs L
cc.complexity-theory
complexity-classes
reductions
polynomial-time
logspace
What is the complexity class most closely associated with what the human mind can accomplish quickly?
cc.complexity-theory
complexity-classes
soft-question
Relation between transcendental numbers and computational complexity?
reference-request
complexity-classes
nt.number-theory
comp-number-theory
How to charactorize computational complexity based on finding solution to algebraic equations?
reference-request
complexity-classes
universal-computation
comp-number-theory
computational-mathematics
An oracle that separates BPP from PP?
cc.complexity-theory
complexity-classes
counting-complexity
oracles
nondeterminism
Presburger arithmetic: is it known to be in $EXPSPACE \setminus EXP$?
cc.complexity-theory
complexity-classes
Random self reducibility and NP
np-hardness
complexity-classes
reductions
On $NP$, $\oplus P$ and $PP$?
cc.complexity-theory
complexity-classes
On reduction between two classes?
cc.complexity-theory
reference-request
complexity-classes
reductions
relativization
What is conjunctive truth table reduction?
cc.complexity-theory
reference-request
complexity-classes
reductions
relativization
Cases of Linear programming known to be in $NC$?
cc.complexity-theory
ds.algorithms
complexity-classes
linear-programming
dc.parallel-comp
Does Kannan's theorem imply that NEXPTIME^NP ⊄ P/poly?
cc.complexity-theory
complexity-classes
time-complexity
oracles
circuits
Problems in NC not known to lie in NC2
complexity-classes
dc.parallel-comp
Problems in $\mathsf{NC^{2}}$ that are not known to be in $\mathsf{AC^{1}}$ or $\mathsf{DET}$
complexity-classes
dc.parallel-comp
Problems outside of P that are not P-hard
cc.complexity-theory
complexity-classes
Recursively presenting or even enumerating all P-hard languages
cc.complexity-theory
complexity-classes
p-hardness
Sufficient conditions for the collapse of Polynomial Hierarchy (PH)
cc.complexity-theory
complexity-classes
big-list
A class of languages admitted by a class of grammars equivalent to $\mathbf{PR}$?
complexity-classes
fl.formal-languages
grammars
What is the computational complexity of solutions over $\mathbb{Q}$ of polynomial equation with coeffiecents over $\mathbb{Z}$
complexity-classes
algebraic-complexity
Two queries related to Toda
cc.complexity-theory
complexity-classes
Proving NP-complete problem
np-hardness
complexity-classes
Are $BPP^{BPP^{\oplus P}}$ and $BPP^{NP}$ contained in $BPP^{\oplus P}$?
cc.complexity-theory
complexity-classes
randomness
oracles
polynomial-hierarchy
Is there any known Poly-APX-complete minimimization problem?
reference-request
complexity-classes
approximation-hardness
approximation
Approximation class of finding decision trees with minimal depth
complexity-classes
approximation-hardness
approximation
query-complexity
decision-trees
Difference between $Max-SNP_0$ and $Max-SNP$
complexity-classes
On collapsing the Exponential time hierarchy
cc.complexity-theory
complexity-classes
lo.logic
oracles
What happens when PSPACE contains NEXP?
cc.complexity-theory
reference-request
complexity-classes
time-complexity
space-complexity
Given an algebraic variaties of n multivarieties polynomial equations, is there any algorithm to decide whether there is n-cube inscribing to it?
complexity-classes
computational-geometry
Almost-P and related definitions
complexity-classes
relativization
random-oracles
#P-complete problem whose decision version is in P
cc.complexity-theory
complexity-classes
counting-complexity
What is the relation between P-immune languages and NP-complete languages?
complexity-classes
fl.formal-languages
computability
When studying the computational complexity of functions $\{0, 1\}^\ast \to \{0, 1\}^\ast$, is it enough to restrict to $\{0, 1\}^\ast \to \{0, 1\}$?
cc.complexity-theory
complexity-classes
time-complexity
Is there an inherently ambiguous language which can not be recognized by Deterministic LBA?
complexity-classes
fl.formal-languages
computability
automata-theory
Time Hierarchies in DSPACE(O(s(n)))
cc.complexity-theory
complexity-classes
turing-machines
space-bounded
time-hierarchy
Is sliding blocks linear space complete?
cc.complexity-theory
complexity-classes
space-complexity
Example of something that’s different for generic and random oracles?
cc.complexity-theory
complexity-classes
In what class are randomized algorithms that err with exactly 25% chance?
cc.complexity-theory
complexity-classes
randomized-algorithms
Complexity Class Equalities on the Edge of Inconsistency
cc.complexity-theory
complexity-classes
circuit-complexity
Is there a language in NSPACE(O(n)) and (very likely) not in DSPACE(O(n))?
cc.complexity-theory
complexity-classes
np-complete
space-complexity
Is Asymptotic PTAS $\subseteq$ APX?
cc.complexity-theory
np-hardness
complexity-classes
approximation-hardness
Classes between $\textbf{PSPACE}$ and $\textbf{EXP}$
cc.complexity-theory
complexity-classes
Power of randomness vs. power of indefinite computation
cc.complexity-theory
complexity-classes
probabilistic-computation
Logarithmic levels of the polynomial hierarchy (below PSPACE)
cc.complexity-theory
complexity-classes
Is there known any complexity class containing online counterparts of optimization problems?
cc.complexity-theory
complexity-classes
Is Norbert Blum's 2017 proof that $P \ne NP$ correct?
cc.complexity-theory
np-hardness
complexity-classes
What are examples of complexity classes that have contradictory relativizations but they were proven to be either equal or unequal?
complexity-classes
oracles
relativization
random-oracles
Tardos Function Counterexample to Blum's $P\neq NP$ Claim
cc.complexity-theory
np-hardness
complexity-classes
An analog of DP for the second level of the polynomial hierarchy
complexity-classes
polynomial-hierarchy
Oracle comparing $EXP$ with $UP$
cc.complexity-theory
complexity-classes
oracles
exp-time-algorithms
relativization
A succinct version of permanent that is $EXP$-complete
cc.complexity-theory
complexity-classes
permanent
succinct
examples
variant of Critical SAT
cc.complexity-theory
complexity-classes
boolean-functions
Dp completeness of a problem
cc.complexity-theory
complexity-classes
polynomial-hierarchy
What does $\#P\subseteq FP^{PPAD}$ imply?
cc.complexity-theory
complexity-classes
counting-complexity
polynomial-hierarchy
ppad
Closure properties of $L$ (DLOGSPACE)?
cc.complexity-theory
complexity-classes
logspace
On $\#P\subseteq FP^{\Sigma_{f(n)}^P}$?
cc.complexity-theory
complexity-classes
permanent
$\mathsf{NP^{PP}}$ vs $\mathsf{P^{PP}}$
complexity-classes
A uniform computability model to define time and space complexity (even in the sublinear case)
cc.complexity-theory
complexity-classes
turing-machines
logspace
definitions
DTIME and PSPACE
cc.complexity-theory
complexity-classes
On status of Valiant's $NC^2=P^{\#P}$ provability program?
cc.complexity-theory
reference-request
complexity-classes
big-picture
polynomial-hierarchy
On $\Delta_i^P$
cc.complexity-theory
complexity-classes
lower-bounds
derandomization
polynomial-hierarchy
How to show this problem is hard?
cc.complexity-theory
np-hardness
complexity-classes
What is the complexity of computation of zero point by Rieman zeta function?
cc.complexity-theory
complexity-classes
comp-number-theory
Co-Partition Problem: Why is this proof for it being in NP wrong?
cc.complexity-theory
complexity-classes
np
${\bf NP} \not = {\bf E}$ and ${\bf PSPACE} \not = {\bf E}$
cc.complexity-theory
complexity-classes
time-complexity
p-vs-np
Descriptive model theory classification of Counting hierarchy
cc.complexity-theory
complexity-classes
descriptive-complexity
finite-model-theory
model-theory
Is there a computing problem which is in quasi-polynomial time but is (maybe) not in $\beta P$?
cc.complexity-theory
complexity-classes
On $NP$ and $XP$ classes?
cc.complexity-theory
reference-request
complexity-classes
big-picture
parameterized-complexity
Consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$
cc.complexity-theory
graph-theory
complexity-classes
sat
counting-complexity
Intermediate problems between PSPACE and EXPTIME
cc.complexity-theory
complexity-classes
exp-time-algorithms
pspace
Complexity of comparison unary>binary
cc.complexity-theory
complexity-classes
complexity
logspace
Can one amplify P=NP beyond P=PH?
cc.complexity-theory
reference-request
complexity-classes
conditional-results
polynomial-hierarchy
Is finding a solution harder than verifying a solution?
ds.algorithms
complexity-classes
A question of relationships between #P and PSPACE
cc.complexity-theory
complexity-classes
turing-machines
k-Vertex Cover problem is in parameterized Log space
cc.complexity-theory
complexity-classes
space-complexity
logspace
Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?
complexity-classes
quantum-computing
Does there exist an oracle $A$ such that $(P^{\#P})^{A} \neq PSPACE^{A}$?
cc.complexity-theory
complexity-classes
oracles
relativization
pspace
Looking for approximation class between NPO and Exp-APX
complexity-classes
approximation-algorithms
approximation-hardness
approximation
Does the existence of an RP-complete language imply P = RP?
cc.complexity-theory
complexity-classes
Running multiple rounds of a BQP computation, without multiple measurements?
complexity-classes
quantum-computing
Why are these two definitions of PPAD equivalent?
cc.complexity-theory
complexity-classes
ppad
Is $\sf{P^{NP \cap coNP}} = \sf{NP \cap coNP}$?
complexity-classes
np
oracles
polynomial-hierarchy
What's the relationship between ASP-complete and #P-complete?
cc.complexity-theory
complexity-classes
counting-complexity
unique-solution