Questions tagged [complexity-classes]
Computational complexity classes and their relations
628
questions
0
votes
1
answer
64
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} = \...
- 171
-1
votes
0
answers
24
views
NCness of unique solution fixed dimension integer programming
Consider the promise problem of fixed dimension integer programming with promise being that there is exactly one witness. The problem is in $TFNP$. If the promise problem is in $FNC$ then integer $GCD$...
- 12.5k
0
votes
0
answers
60
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 ...
- 429
0
votes
0
answers
66
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,695
3
votes
2
answers
215
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,695
0
votes
1
answer
173
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 ...
- 39
4
votes
0
answers
107
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
78
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 ...
- 429
5
votes
0
answers
102
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
322
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 ...
- 349
-1
votes
1
answer
91
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
181
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,623
2
votes
0
answers
76
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,623
6
votes
1
answer
155
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 ...
- 171
0
votes
0
answers
83
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
74
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
110
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
78
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
182
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
206
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
284
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
104
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
372
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
163
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
235
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
147
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
191
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
113
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
197
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.5k
2
votes
0
answers
210
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.5k
2
votes
1
answer
72
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 ...
- 153
1
vote
1
answer
181
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
214
views
anything hinting that EXPTIME $\subseteqq$ PSPACE?
Anything or evidence hinting that $$EXPTIME \subseteqq PSPACE$$？
- 1,059
1
vote
0
answers
78
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 ...
- 153
1
vote
0
answers
197
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
3
votes
0
answers
130
views
Complexity of real coefficients Linear Programs
I would like to know if there are known any polynomial time algorithms for deciding the feasibility of linear programs with real (not integers) coefficients.
I know that for linear programs with ...
- 131
3
votes
0
answers
158
views
Improving the approximation in Stockmeyer's counting theorem
Given a $\#P$ function $f(x)$, we can use Stockmeyer's counting theorem to get an approximation $g(x)$ such that
\begin{equation}
\left(1 - \frac{1}{\text{poly}(n)} \right) f(x) \le g(x) \le \left(...
- 153
2
votes
0
answers
100
views
Consequences of an $o(\log n)$-approximation algorithm for a $\mathsf{\log\text{-}APX}$ hard problem
In [1], Feige proves that if there is a polynomial algorithm with approximation ratio in $o(\log n)$ for any $\mathsf{log\textit{-}APX}$ hard problem (say Minimum Dominating Set), then $\mathsf{NP}\...
- 1,131
3
votes
1
answer
133
views
What is the best simulation of majority utilizing $\bmod\{2,3,\dots,p\}$ gates?
It is known $AC^0[2]$ cannot get majority function.
Is there a literature on simulation of $MAJ$ function utilizing $AC^0[2,3,\dots,p]$ gates for a finite fixed set of primes $2$ to $p=O(1)$?
What is ...
- 12.5k
0
votes
0
answers
73
views
On Determinant modulo $2^k$ complexity
Determinant of integer matrix modulo $2$ is complete for the class $\oplus L$. Is determinant modulo $2^k$ computable in $\oplus L$ at any fixed $k$?
How about if $k=o(n)$ where matrix is $n\times n$?
- 12.5k
4
votes
0
answers
169
views
The graph of problem reductions
A classical approach to study the complexity of a problem $P$ is to efficiently reduce a well known problem $P'$ to $P$, thus showing that $P$ is at least as difficult as $P'$. The TCS literature ...
- 683
0
votes
1
answer
161
views
Comparing SAT to MCSP reduction class separations and faster SAT class separations?
Assume $SAT$ is in $QuasiP$. We immediately infer $NQuasiP=QuasiP$ and $EXP=NEXP$. From https://people.csail.mit.edu/rrw/easy-witness-nqp.pdf we infer $NQuasiP$ is not in $P/poly$ which implies $...
- 12.5k
0
votes
0
answers
56
views
Is anything known about NC$^1$ with NP oracle
A few things are known about the class $\textsf{L}$ provided with an $\textsf{NP}$ oracle ($\textsf{L}^\textsf{NP} = \Theta_2^\textsf{P}$ has attracted a bit of attention, for instance [1]) On the ...
- 793
2
votes
0
answers
61
views
Logarithmic queries to $\Sigma_i^P$ oracle and the Boolean hiearchies
If I understood correctly (the complexity zoo, wikipedia, and some of the cited articles), the class $\textsf{P}^{\textsf{NP}[\log]}$, also known as $\Theta_2^{\textsf{P}}$, sits at the top of the ...
- 793
5
votes
1
answer
344
views
Where is $MA$ more relevant than $\exists BPP$?
NP can be defined as the class of languages which admit sets of certificates which are in P. The definition could be as follows.
A language $L$ is in $NP$ iff there is a set $C=\left\{ x,c\right\}$ ...
- 91
0
votes
0
answers
117
views
$\mathsf{ACC}^0$ and $\mathsf{TC}^0$ with $\mathsf{Cuniform}$-$\oplus\mathsf{L}$ or $\mathsf{Cuniform}$-$\mathsf{NC}^1$ oracle?
$\mathsf{TC}^0$ is a small class with $\oplus\mathsf{L}$ containing it.
Following inclusions are known:
$$\mathsf{Cuniform}\mbox{ -}\mathsf{ACC}^0\subseteq\mathsf{Cuniform}\mbox{ -}\mathsf{TC}^0\...
- 12.5k
2
votes
1
answer
117
views
Is there any relation between $\mathsf{PPP}\subseteq\mathsf{TFNP}$ and $\mathsf{UP}$? [closed]
A complete problem for $\mathsf{PPP}$ is the pigeon problem which is 'Given a Boolean circuit ${\displaystyle C}$ having the same number ${\displaystyle n}$ of input bits as output bits, find either ...
- 12.5k