Questions tagged [complexity-classes]
Computational complexity classes and their relations
640
questions
3
votes
1
answer
194
views
Relativized world in which P ≠ NP = coNP
Do we know of an oracle relative to which P ≠ NP but NP = coNP?
- 547
4
votes
0
answers
91
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,787
-3
votes
0
answers
76
views
Relation between $NC^i$ and $L^i$
Is it true $NC^i\subseteq L^i\subseteq NC^{i+1}$ at every $i>0$?
- 12.6k
2
votes
0
answers
120
views
Is modular square roots in NC?
Assume factorization of modulus is known. Is modular square roots then in $NC$?
How about the case of prime modulus?
- 12.6k
5
votes
1
answer
107
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 $...
- 195
0
votes
0
answers
91
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 \...
- 547
1
vote
0
answers
64
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.6k
2
votes
0
answers
94
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
66
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
55
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,402
4
votes
1
answer
143
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
67
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.6k
0
votes
0
answers
72
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.6k
0
votes
1
answer
100
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
66
views
What is the right notion of reduction for 2EXPTIME?
I've recently been working on some temporal logic problems. In particular, a central result in the field is the fact that realizability for LTL is 2EXPTIME-complete. I've only seen the result quoted ...
- 547
0
votes
0
answers
69
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,787
3
votes
2
answers
257
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,787
0
votes
1
answer
196
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
116
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 ...
- 141
1
vote
0
answers
81
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 ...
- 547
5
votes
0
answers
113
views
Are there well-accepted attempts of people to create complexity classes in continuous time?
I'm not in CS theory, but I've talked to a complexity theorist recently who, in passing, suggested that my research (not really analog computing, but hypercomputation using physical systems in ...
5
votes
3
answers
329
views
Are there any problems whose best known algorithms have running time $n^{\log \log n}$?
It’s well known that problems such as integer factorization have running times contained in $e^{\text{Poly} \log }$ which is the same $n^{ \text{Poly} \log }$ (actually the log term is itself in a ...
- 369
-1
votes
1
answer
116
views
Showing that a modification of an NP-Complete problem is also NP-Complete
In this question I give a modified version of the knapsack problem, which I call the "extended knapsack problem". I want to show that this "extended" problem is NP-Complete, but I ...
- 99
0
votes
0
answers
68
views
Simplify or bound using Big-O notation
I was following a research paper which have the following equation:
$\left(1-\frac{1}{K}\right)^{K-i}\left[1-\left(1-\frac{1-p}{K}\right)^{i}\right]=\frac{i(1-p)}{K}+O\left(\left(\frac{i}{K}\right)^{2}...
- 99
2
votes
1
answer
191
views
Complexity of the Complete (3,2) SAT problem?
A complete $k$-CNF formula is a $k$-CNF formula which contains all clauses of size $k$ or lower it implies.
Deciding the satisfiability of a complete $k$-CNF formula is clearly a tractable problem ...
- 1,069
0
votes
0
answers
37
views
Is there an MMSNP formula for 3-colouring?
By MMSNP, I mean Monotone Monadic SNP without inequality. For $k\in\mathbb{N}$, the problem $k$-COLOURABILITY takes a graph $G$ as input and asks whether $G$ is $k$-colourable.
It is well-known that ...
- 1,633
2
votes
0
answers
78
views
Nondeterministic polynomial time languages with linearly bounded certificates
Define the class $X$ of languages by the condition that a language $L$ over alphabet $\Sigma$ is in $X$ iff there are a constant $c > 0$ and a polynomial-time checking relation $R$ such that for ...
- 91
0
votes
0
answers
78
views
Does NP-completeness in one graph class imply not NP-intermediate in another graph class?
I am trying to wrap my head around implications of CSP dichotomy theroem.
CSP is short for Constraint Satisfaction Problem.
The following seem to be known results (I shall focus on decision problems ...
- 1,633
6
votes
1
answer
161
views
Reductions weaker than polynomial-time for $\exists \mathbb{R}$
I am currently studying the complexity class $\exists \mathbb{R}$ which contains all problems that are reducible in polynomial time to the existential theory of the reals. In the literature ...
- 173
0
votes
0
answers
86
views
What are the capabilities of current Boolean Satisfiability Solvers?
I am wondering how well current Boolean Satisfiability solvers are able to perform — for example, are the best SATsolvers able to solve problems from SATlib?
- 1
3
votes
0
answers
79
views
Complete problems for fast-growing hierarchy classes
I need examples of natural complete problems in classes $\textbf{F}_\alpha$, definition of $\textbf{F}_\alpha$ can be found here. Also in section 6 there are examples for $\omega$, $\omega^\omega$, $\...
- 49
0
votes
1
answer
117
views
Question about BPP complexity class [closed]
Good morning everyone, I just started studying the BPP complexity class and the amplification lemma. There is one exercise about BPP that I don't understand, I hope that you can help me.
Let $L$ be a ...
- 13
0
votes
0
answers
99
views
APX-hardness of Max-3-SAT(5)
Max-3-SAT($k$) for a natural number $k$ is the task of finding the maximum number of satisfiable clauses in a Boolean formula in CNF, where every clause contains at most 3 literals and every variable ...
- 11
0
votes
1
answer
186
views
Is there a precise definition for big O notation with 2 or more variables [closed]
Big O notation has a very precise definition for 1 variable. You can prove O(2x^2) = O(x^2) for example. There is never ambiguity. However, for 2 or more variables ...
- 111
6
votes
1
answer
213
views
Complexity of reachability in directed rooted forests
I'm trying to figure out the complexity of the reachability problem having as input a directed rooted forest, i.e., given a set of directed rooted trees and two vertices $s$ and $t$, tell if $s$ and $...
- 133
6
votes
1
answer
287
views
What is the complexity of HORN-2CNF entailment?
I know the entailment of a propositional variable in a HORN-3CNF formula is $P$-complete.
I can't find any publication in which it has been shown the complexity of the same problem for HORN-2CNF ...
- 133
0
votes
0
answers
116
views
Query about P/poly and Polynomial Hierarchy Collapse to $\Sigma _{2}$
I am not conversant in the complexity class $P/poly$. While reading about the class on wiki I encountered two conditional statements about it, namely:
If $NP ⊆ P/poly$ then $PH$ (the polynomial ...
- 811
8
votes
1
answer
441
views
Complete problem in $\Sigma_2^p$ - $\Sigma_{2}SAT$
It is known that the following problem is complete in $\Sigma_2^p$:
$\Sigma_{2}SAT$ : Given a quantified boolean formula $\theta = \exists x_1,...,x_l\forall y_1,...,y_m\psi$, where $\psi$ is a ...
3
votes
1
answer
164
views
complexity class of a function - linear combinations and reductions (Fermionant, immanant, $GL_n$ representations)
The fermionant is a matrix function from physics, which is indexed by a positive integer $k$:
\begin{align}
\operatorname{Ferm}_k(A) = \sum_{\lambda} d_{\lambda}^{(k)} \operatorname{Imm}_{\lambda^T}(A)...
- 31
7
votes
1
answer
254
views
What is the complexity class of higher-order primitive recursion?
Short and sweet: The complexity class of primitive recursive functions (WP) is PR (WP, Zoo). What's the complexity class of higher-order primitive recursion (WP)?
The motivating context is simply that ...
- 243
1
vote
1
answer
156
views
Is QMA known to contain Co-NP?
Is QMA known to contain Co-NP? If not, would Co-NP being contained in QMA have any implications for other complexity classes. (e.g. Causing the polynomial heirachy to collapse.)
- 177
0
votes
1
answer
197
views
Lexicographic Boolean satisfiability
Maximal Satisfying Assignment (Lexicographic Boolean satisfiability / LexMaxSAT), the problem of finding the lexicographically maximum x_1, . . . , x_n ∈ {0, 1}^n that satisfies Boolean formula φ, or ...
3
votes
0
answers
115
views
Complete problems for $(NP\cap CoNP)/poly$ class and universal representations
It is conjectured that $NP\cap CoNP$ does not have a complete problem with respect to the polynomial-time many-to-one reductions. I would like to know the current knowledge about the nonuniform ...
- 322
4
votes
0
answers
199
views
What does width $4$ permutation branching program correspond to?
$L$ can be computed by a family of programs over $S_3$
of polynomial length if and only if $L$ can be computed by a family of $MOD3 ◦ MOD2$ circuits of
polynomial size.
$L$ can be computed by a family ...
- 12.6k
2
votes
0
answers
212
views
Simultaneous evidence for $L\neq NL$ and $P\neq NP$
We believe $L\neq NL$ and $P\neq NP$.
Is there any evidence which simultaneously imply $L\neq NL$ and $P\neq NP$?
- 12.6k
2
votes
1
answer
77
views
Relative error estimation of a special type of GapP function
Consider the functions included in the complexity class GapP.
We know that approximating a function from GapP, in the worst case, to inverse polynomial multiplicative error, is #P-hard. Even correctly ...
- 163
1
vote
1
answer
207
views
KRW Conjecture: separation of NC^1 and P
More than a real question this is a recap of something I have been studying. I hope someone will help me getting things straight, so any correction or thought about the following reasoning is more ...
1
vote
0
answers
216
views
anything hinting that EXPTIME $\subseteqq$ PSPACE?
Anything or evidence hinting that $$EXPTIME \subseteqq PSPACE$$？
- 1,050
1
vote
0
answers
80
views
Additive error approximations of GapP functions
Consider a GapP function $g(x)$ for $x \in \{0, 1\}^{*}$. Consider an approximation $\tilde g(x)$ such that
\begin{equation}
\left|g(x) - \tilde g(x)\right| \leq \epsilon.
\end{equation}
Consider a ...
- 163
1
vote
0
answers
202
views
IP, MIP and MIP* with super-polynomial verifier
Regarding each of the above classes, what are the currently known upper bounds when the verifier is given more than polynomial power?
Specifically, when do we reach ALL in each of the above classes ...
- 1,526