Questions tagged [complexity-classes]

Computational complexity classes and their relations

Filter by
Sorted by
Tagged with
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?
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 $\...
-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 $...
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 \...
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 ...
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 ...
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 ...
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 ...
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 ...
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-...
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 ...
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 ...
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 ...
-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 ...
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}...
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 ...
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 ...
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 ...
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?
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 ...
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 $...
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 ...
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 ...
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.)
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 ...
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 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

1
2 3 4 5
13