Questions tagged [complexity-classes]
Computational complexity classes and their relations
667
questions
8
votes
1
answer
346
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 ...
- 609
1
vote
0
answers
63
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
0
votes
0
answers
97
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
2
votes
1
answer
277
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 ...
user70406
5
votes
1
answer
384
views
Relation between ACC^0 and DTIME
In a breakthrough Ryan Williams (STOC13/14) showed that $\mathsf{NEXP} \nsubseteq \text{non-uniform } \mathsf{ACC}^0$.
How far can we potentially push this result?
In other words, what is the largest $...
- 223
0
votes
0
answers
165
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 ...
- 101
3
votes
0
answers
111
views
Computational complexity of finding the $n$th Dedekind Number
Recently, two independent groups of researchers exactly calculated the $9$th Dedekind Number (see e.g. Quanta). The $n$th Dedekind Number counts the number of antichains consisting of subsets of $\{1,...
- 205
1
vote
1
answer
108
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, ...
- 13
5
votes
0
answers
125
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,416
1
vote
0
answers
77
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.
...
- 900
7
votes
1
answer
293
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 ...
- 321
1
vote
0
answers
131
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
6
votes
3
answers
328
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
7
votes
0
answers
188
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,181
3
votes
1
answer
173
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
2
votes
0
answers
42
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 ...
- 245
0
votes
0
answers
67
views
Are there any examples of problems in ZPP not yet in P?
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
9
votes
1
answer
286
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
0
votes
0
answers
41
views
What the relation between the classes SC and NC?
What the relation between the classes SC (Scott's class) and NC? (Nick's class).
Is SC contained in NC?
Is NC contained in SC?
- 177
3
votes
0
answers
101
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
1
answer
101
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
10
votes
1
answer
805
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
7
votes
0
answers
171
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
3
votes
1
answer
224
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,086
1
vote
0
answers
85
views
Perm and Det mod $2^k$ - II
Given a $0/1$ square matrix, the permanent and determinant modulo $2^k$ is in $\oplus P$ and $\oplus L$ respectively for any fixed $k$. In fact both are in $\oplus L$ (in fact in $\oplus SPACE(k^2\log ...
- 12.8k
2
votes
0
answers
77
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
2
votes
1
answer
99
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 ...
- 1,973
6
votes
0
answers
152
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 ...
- 61
2
votes
0
answers
36
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(...
- 21
3
votes
0
answers
99
views
$\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 ...
- 131
0
votes
0
answers
138
views
On the use of Turing machines for computational complexity
Almost always in the study of computational complexity, the Turing machine is used as a model. On the other hand, the untyped lambda calculus is in a sense "simpler" than any Turing machine: ...
1
vote
0
answers
69
views
Is NLOGTIME self-low?
https://en.wikipedia.org/wiki/Low_(complexity)
Every class which is low for itself is closed under complement, provided that it is powerful enough to negate the boolean result. EXP, which is closed ...
- 111
3
votes
1
answer
247
views
Relativized world in which P ≠ NP = coNP
Do we know of an oracle relative to which P ≠ NP but NP = coNP?
- 801
4
votes
0
answers
106
views
$\mathsf{NL}$ vs. $\mathsf{AC}^1$
It is known that $\mathsf{NL} \subseteq \mathsf{AC}^1$ (because $\mathsf{NL}$-complete problem PATH belongs to $\mathsf{AC}^1$).
Are there problems in $\mathsf{AC}^1$ that are unknown to be in $\...
- 1,973
3
votes
1
answer
248
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.8k
5
votes
1
answer
125
views
DET is $VQP-complete$ and also $DET\in VP$ Does that mean $VP=VQP$
We know that $DET$ is in $VP$. And also from https://conferences.mpi-inf.mpg.de/adfocs-17/material/MB_LN.pdf I came to know that $DET$ is $VQP-complete$. Now certainly $VP\subseteq VQP$. That implies $...
- 288
0
votes
0
answers
96
views
Non-uniformity assumptions in circuit complexity
I recently came accross the following standard inclusion of complexity classes:
$$\textbf{NC}^0 \subseteq \textbf{AC}^0 \subseteq \textbf{NC}^1 \subseteq \textbf{L} \subseteq \textbf{NL} \subseteq \...
- 801
1
vote
0
answers
72
views
One way analogues of Logspace
When we say a function is one-way we typically mean a function is encodable in $P$ but its decryption is not in $P$ but in $UP$.
Likewise we say a function is logspace one-way if the function is ...
- 12.8k
2
votes
0
answers
107
views
Problems in $P^{PP}$
I just discovered that a problem that I was studying could belong to $P^{PP}$, I would like to prove that this problem is $P^{PP}$-complete (if that is even a thing). The issue is that I'm unable to ...
- 21
0
votes
0
answers
73
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 ...
- 21
2
votes
1
answer
65
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,537
4
votes
1
answer
167
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
2
votes
0
answers
77
views
Parallel complexity of fixed dimension fixed constraints integer programming
Papadimitriou in https://lara.epfl.ch/w/_media/papadimitriou81complexityintegerprogramming.pdf shows ILP is fixed parameter tractable in number of constraints and Lenstra in https://people.csail.mit....
- 12.8k
0
votes
0
answers
90
views
Boolean vs algebraic circuits difference
Valiant, Skyum, Berkowitz and Rackoff in https://epubs.siam.org/doi/10.1137/0212043 showed that $VP=VNC^2$, namely, that arithmetic circuits can be parallelized.
What is the central reason such a ...
- 12.8k
0
votes
1
answer
112
views
On the proof of $PP = P \iff \#P = FP$ in Arora & Barak (Lemma 17.7)
Introduction
I am currently studying chapter 17 (of the famous textbook by Arora & Barak [1]) on the complexity of counting and got stuck on the proof of Lemma 17.7, which states $\mathrm{PP} = \...
- 173
0
votes
0
answers
72
views
Interactive proofs with computation bounded Merlin
Consider usual interactive proofs (Arthur is polynomial-time bounded and can use random bits)
where computation power of Merlin is bounded by polynomial-size circuits.
For example, every unary NP-...
- 1,973
3
votes
2
answers
291
views
Classes between PH and PSPACE
I am interesting in languages of the following form:
$x \in L \Leftrightarrow Q y_1 Q y_2 \ldots Q y_n P(x, y_1, \ldots y_n, x).$
Here every Q is $\forall$ or $\exists$;
$n$ is the length of $x$, the ...
- 1,973
0
votes
1
answer
215
views
What Complexity Class is this? Is this already known?
Let's call this the Path Game.
For this example, lets imagine a 16x16 grid:
Some of the squares in this grid are "deadly." If you step on it, you must restart and try to go over again. We ...
- 21
4
votes
0
answers
148
views
What is the intuition behind P/qpoly=P/poly?
I very much struggle to understand the qualitative differences between anything/qpoly. For exampe we read at Watrus that
BQP/qpoly essentially are the decision problems that are solved by
polynomial ...
- 183
2
votes
0
answers
105
views
Gurevich's theorem on primitive recursive functions being logspace-computable
I recently came across the following result attributed to Gurevich, according to which I understood that the class of problems solvable by primitive recursive functions is precisely the class L of ...
- 801