Questions tagged [complexity-classes]

Computational complexity classes and their relations

Filter by
Sorted by
Tagged with
0 votes
0 answers
94 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 ...
Turbo's user avatar
  • 12.9k
0 votes
1 answer
120 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} = \...
sebastian's user avatar
  • 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-...
Alexey Milovanov's user avatar
3 votes
2 answers
305 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 ...
Alexey Milovanov's user avatar
0 votes
1 answer
223 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 ...
Bapcap's user avatar
  • 21
4 votes
0 answers
158 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 ...
Marion's user avatar
  • 183
2 votes
0 answers
117 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 ...
Noel Arteche's user avatar
5 votes
0 answers
125 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 ...
Daniel Primosch's user avatar
5 votes
3 answers
350 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 ...
Sidharth Ghoshal's user avatar
-1 votes
1 answer
136 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 ...
user918212's user avatar
2 votes
1 answer
216 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 ...
Xavier Labouze's user avatar
2 votes
0 answers
82 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 ...
Alberto's user avatar
  • 191
0 votes
0 answers
83 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 ...
Cyriac Antony's user avatar
6 votes
1 answer
193 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 ...
sebastian's user avatar
  • 173
0 votes
0 answers
91 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?
Nat Kar's user avatar
3 votes
0 answers
93 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$, $\...
Ben Tom's user avatar
  • 49
0 votes
1 answer
145 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 ...
John Mayer's user avatar
0 votes
1 answer
200 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 ...
mousetail's user avatar
  • 111
6 votes
1 answer
260 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 $...
Abel Freid's user avatar
6 votes
1 answer
296 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 ...
Abel Freid's user avatar
0 votes
0 answers
177 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 ...
TheoryQuest1's user avatar
8 votes
1 answer
841 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 ...
Naama Shamash Hal's user avatar
3 votes
1 answer
171 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)...
Teferi's user avatar
  • 31
8 votes
1 answer
335 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 ...
Corbin's user avatar
  • 271
1 vote
1 answer
169 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.)
blademan9999's user avatar
0 votes
1 answer
220 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 ...
user63167's user avatar
3 votes
0 answers
121 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 ...
Erfan Khaniki's user avatar
4 votes
0 answers
219 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 ...
Turbo's user avatar
  • 12.9k
2 votes
0 answers
213 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$?
Turbo's user avatar
  • 12.9k
2 votes
1 answer
90 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 ...
AngryLion's user avatar
  • 173
1 vote
1 answer
287 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 ...
Pietro D'Amico's user avatar
1 vote
0 answers
224 views

anything hinting that EXPTIME $\subseteqq$ PSPACE?

Anything or evidence hinting that $$EXPTIME \subseteqq PSPACE$$?
XL _At_Here_There's user avatar
1 vote
0 answers
106 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 ...
AngryLion's user avatar
  • 173
1 vote
0 answers
220 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 ...
Avi Tal's user avatar
  • 1,606
4 votes
0 answers
136 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 ...
C Marius's user avatar
  • 141
4 votes
0 answers
320 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(...
AngryLion's user avatar
  • 173
2 votes
0 answers
104 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}\...
Lamine's user avatar
  • 1,138
3 votes
1 answer
135 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 ...
Turbo's user avatar
  • 12.9k
0 votes
0 answers
81 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$?
Turbo's user avatar
  • 12.9k
4 votes
0 answers
176 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 ...
Matthieu Latapy's user avatar
0 votes
1 answer
192 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 $...
Turbo's user avatar
  • 12.9k
0 votes
0 answers
61 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 ...
Abdallah's user avatar
  • 803
2 votes
0 answers
73 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 ...
Abdallah's user avatar
  • 803
6 votes
1 answer
559 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\}$ ...
J.Ask's user avatar
  • 101
0 votes
0 answers
120 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\...
Turbo's user avatar
  • 12.9k
2 votes
1 answer
132 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 ...
Turbo's user avatar
  • 12.9k
5 votes
1 answer
261 views

Is there a containment between $\mathsf{ZPP}$ and $\mathsf{UP}$?

Do we know if $\mathsf{ZPP}\subseteq\mathsf{UP}$ known or is there oracles against the hypothesis?
Turbo's user avatar
  • 12.9k
16 votes
2 answers
516 views

NLOGTIME versus $\exists$DLOGTIME

$\def\dlt{\mathrm{DLOGTIME}}\def\nlt{\mathrm{NLOGTIME}}\def\mr{\mathrm}$During a recent discussion on another question, I mentioned a factoid $\exists\dlt=\nlt$, but then I realized that I may have ...
Emil Jeřábek's user avatar
12 votes
0 answers
356 views

NP complete problem help

I'm currently trying to find a reduction to this problem: Given a set S of n points (in the plane) in general position, is there a set of at least k triangles (formed using only points in S as ...
Andres Fuentes's user avatar
4 votes
0 answers
105 views

Is it to solid to conclude APX-complete after showing a problem cannot be approximated better than 1.5 and also develop a 2-approximation algorithm

I know the canonical way to show APX-Complete is to give an L-reduction from an already-known APX-complete problem. If I have used gap-preserving reduction to show a problem cannot be approximated ...
Wenkai's user avatar
  • 41

1
2
3 4 5
14