Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [complexity-classes]

Computational complexity classes and their relations

194 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
30 votes
0 answers
794 views

The complexity of checking whether two DAG have the same number of topological sorts

This problem is highly related to the CNF one. Here is the problem: given two DAG (directed acyclic graphs), if they have the same counting of topological sorts, answer "Yes", otherwise, answer "No". ...
Mike Chen's user avatar
  • 709
29 votes
0 answers
1k views

Does $EXP\neq ZPP$ imply sub-exponential simulation of BPP or NP?

By simulation I mean in the Impaglazzio-Widgerson [IW98] sense, i.e. sub-exponential deterministic simulation which appears correct i.o to every efficient adversary. I think this is a proof: if $EXP\...
Sebastian Ben Daniel's user avatar
22 votes
0 answers
783 views

What is the power of general poly-size permutation branching programs?

Call $\mathsf{PPBP}$ the class of languages decided by poly-size families of permutation branching programs, which are layered branching programs (i.e., the ones defined here) whose transitions ...
Damiano Mazza's user avatar
21 votes
0 answers
281 views

Descriptive complexity characterization of TimeSpace classes

Are there descriptive complexity characterizations for TimeSpace complexity classes like $\mathsf{SC^i}= \mathsf{DTimeSpace}(n^{O(1)},O(\lg^i n))$?
Kaveh's user avatar
  • 21.7k
20 votes
0 answers
483 views

Interesting PCP characterization of classes smaller than P?

The PCP theorem, $\mathsf{NP} = \mathsf{PCP}(\mathsf{log}\, n, 1)$, involves probabilistically checkable proofs with polynomial time verifiers, so the smallest class that can be characterized in this ...
argentpepper's user avatar
  • 2,281
17 votes
0 answers
387 views

Intermediate problems between PSPACE and EXPTIME

Intermediate problems between P and NP are quite famous, and are sometimes considered as complexity classes by themselves. Do you know of any problem that is known to be PSPACE-hard and in EXPTIME, ...
Denis's user avatar
  • 8,883
17 votes
0 answers
511 views

What if an $\mathsf L$-complete problem has $\mathsf{NC}^1$ circuits? More generally, what evidence is there against $\mathsf{NC}^1=\mathsf{L}$?

Edit: let me reformulate the question in a more specific way (and change the title accordingly). A slightly edited version of the original question follows. Is there a result comparable to the Karp-...
Damiano Mazza's user avatar
15 votes
0 answers
495 views

An algebra of complexity classes

A key feature of unrelativized computation is its composability out of smaller fragments, and to partially capture the composability, I came up with an algebra of fine-grained complexity classes. For ...
Dmytro Taranovsky's user avatar
15 votes
0 answers
515 views

Williams' Method, Natural Proofs and Constructivity

I have some questions on the previous question which is written bellow. Natural Proof and Constructivity : The topic of the previous question Recently, Ryan Williams proved that Constructivity in ...
atsu's user avatar
  • 171
15 votes
0 answers
346 views

Intersecting Complexity Classes with Advice

In on hiding information from an oracle, the authors (Abadi, Feigenbaum, and Kilian) wrote: $(\mathsf{NP/poly} \cap \mathsf{co\text-NP}{/poly})$ ... is not known to be equal to $(\mathsf{NP}...
Sadeq Dousti's user avatar
  • 16.5k
14 votes
0 answers
474 views

Is there a P-complete language X such that succinct-X is in P?

I came across a paper called "A Note on Succinct Representation of Graphs". It seems that in the discussion section they claim that for any problem $X$ that is $\mathrm{P}$-hard under projections, $\...
Michael Wehar's user avatar
14 votes
0 answers
530 views

Does ${\bf L} \neq {\bf NL}$ imply ${\bf P} \neq {\bf NP}$?

This question is inspired by this question Implications between $\mathsf{L}=\mathsf{P}$ and $\mathsf{NL}=\mathsf{NP}$? We do know that ${\bf L}$ could equal ${\bf NL}$ and at the same time ${\bf P}$ ...
user18304's user avatar
  • 141
14 votes
0 answers
233 views

Do circuits allow to derive EXPSPACE hardness results?

It seems that encoding an NP-complete problem succinctly often makes it nexptime-complete. For instance, 3SAT or HAMILTONIAN PATH become NEXPTIME-complete when the encoding is succint, eg using ...
Abdallah's user avatar
  • 803
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
12 votes
0 answers
690 views

Impact of proof of NP=co-NP on RP vs co-RP Question?

It is known that P ⊆ RP ⊆ NP and P ⊆ co-RP ⊆ co-NP. In an oracle world: If NP=co-NP, does RP=co-RP=ZPP follow automatically or does it require additional conditions? If NP=PSPACE, does RP=co-RP=ZPP ...
TheoryQuest1's user avatar
12 votes
0 answers
408 views

Is it known that $NEXP = \Sigma_2 \implies NEXP = MA$?

Is it known whether the implication $\mathsf{NEXP} = \Sigma_2 \implies \mathsf{NEXP} = \mathsf{MA}$ holds? (The question is inspired by well-known $\mathsf{NEXP} \subseteq \mathsf{P/poly} \...
sdcvvc's user avatar
  • 1,291
12 votes
0 answers
376 views

Oracle relative to which MA does not have a complete problem?

Babai introduced a hierarchy of complexity classes based on public-coin randomized interactive proof systems, so called Arthur-Merlin games. The game is played by powerful but untrustworthy wizard ...
Dai Le's user avatar
  • 3,664
11 votes
0 answers
343 views

Is unary $\Pi_2$-SUBSETSUM coNP-complete?

Consider the following problem: for given integers $a_1, \ldots, a_{2n}$ and $A$ that are given in unary representation define is it true that for every $S \subseteq \{1, ..., 2n \}$ such that $|...
Alexey Milovanov's user avatar
11 votes
0 answers
279 views

Computational Complexity of the Frobenius Problem

The Frobenius problem takes as input $n$ positive integers $a_1,\ldots,a_n$ with $\gcd(a_1,\ldots,a_n)=1$ and asks for the largest integer $F$ that cannot be written in the form $F=a_1x_1+a_2x_2+\...
Alexis's user avatar
  • 219
11 votes
0 answers
200 views

Problems in $\mathsf{NC^{2}}$ that are not known to be in $\mathsf{AC^{1}}$ or $\mathsf{DET}$

Do we know of any problems in $\mathsf{NC^{2}}$ that are not known to be in $\mathsf{AC^{1}}$ or $\mathsf{DET}$? Context: based on Josh's answer to this question, it could be possible that all ...
xal's user avatar
  • 439
11 votes
1 answer
624 views

What is the complexity of counting the number of solutions of a P-Space Complete problem? How about higher complexity classes?

I guess it would be called #P-Space but I have found only one article vaguely mentioning it. How about the counting version of EXP-TIME-Complete, NEXP-Complete as well as EXP-SPACE-Complete problems? ...
Tayfun Pay's user avatar
  • 2,598
10 votes
0 answers
227 views

On Courcelle's question about Monadic second-order logic with cardinality predicates

I have found the following question at openproblemgarden.org: The problem concerns the extension of Monadic Second Order Logic (over a binary relation representing the edge relation) with the ...
Alexey Milovanov's user avatar
9 votes
0 answers
183 views

Complexity of fractional SAT

Let $(a, k)$-SAT be $k$-SAT with the promise that if there is there is a satisfying assignment, then there is such an assignment that satisfies at least $a$ literals of every clause. Can 3-SAT with $...
Dmytro Taranovsky's user avatar
9 votes
0 answers
144 views

Logarithmic levels of the polynomial hierarchy (below PSPACE)

We generally define $PH = \cup_i\Sigma_i^p$ (or various equivalent forms.) In the same notation we can also define $PSPACE = \cup_c\Sigma_{n^c}^p$--that is, like the polynomial hierarchy, but with a ...
ahh's user avatar
  • 223
9 votes
0 answers
534 views

Why do we believe $\mathsf{fewP \ne NP}$?

$\mathsf{fewP}$ ($\mathsf{NP}$ with few witnesses, see the zoo) is one of the important ambiguity-bounded sub-classes of $\mathsf{NP}$. There are interesting natural problems in this class that are ...
Mohammad Al-Turkistany's user avatar
9 votes
1 answer
597 views

Indications that strengthen the conjecture: NEXP ⊊ EXP^NP

I am trying to find indications that strengthen the conjecture of NEXP ⊊ EXP^NP. Clearly NEXP ⊆ EXP^NP, and there are some hints that this inclusion is proper. Some Examples: 1. A paper by Shuichi ...
Avi Tal's user avatar
  • 1,606
8 votes
0 answers
393 views

A canonical complete problem for EXP and NEXP in terms of formulae

3SAT is a complete problem for NP. TQBF is a complete problem for PSPACE. Is there direct way to define canonical complete problems for EXP and NEXP in terms of boolean formulae? I have only seen ...
Turbo's user avatar
  • 12.9k
8 votes
0 answers
148 views

Can we define a meaningful concept of exptime reductions (as opposed to polytime reductions) for classes like NEXP or NEEXP?

Typically we are only interested in polytime reductions as we are usually interested in showing a reduction from one NP-problem to another. However, if we consider larger complexity classes such as ...
Hans Schmuber's user avatar
8 votes
0 answers
349 views

Linear space language that requires exponential time without ETH

The $\mathsf{P} \neq \mathsf{PSpace}$ conjecture means that There is a language $L \in \mathsf{DSpace}(O(n^t))$ for some $t>0$ such that for all positive integers $k$, $L$ requires $\Omega(n^k)...
Jeremy Kun's user avatar
  • 1,318
8 votes
0 answers
637 views

A generalisation of one-wayness

$\mathbf{NP}$-complete problems are worst-case hard. Their average-case counterpart are one-way functions. Is there an analogous one-wayness notion for $\mathbf{coNP}$-complete problems? More ...
Pooya Farshim's user avatar
7 votes
0 answers
216 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. ...
user3483902's user avatar
  • 1,261
7 votes
0 answers
188 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 ...
Manuel Eberl's user avatar
7 votes
0 answers
124 views

What can we say about AM[log n]?

It is known that $\textbf{AM}[O(1)] = \textbf{AM}$. Since $\textbf{IP}=\textbf{PSPACE}$ we have $\textbf{AM}[poly(n)] = \textbf{PSPACE}$. Can we say something about $\textbf{AM}[ f(n)]$, where $f$ ...
Alexey Milovanov's user avatar
7 votes
0 answers
321 views

Why is it so difficult to study Sum of Squares (SoS) algorithms with degree $d>4$?

In many publications on the computational complexity of Sum of Squares (SoS) algorithms, it is typical to study the degree-$4$ relaxation; e.g. Rounding Sum-of-Squares Relaxations Sum-of-Squares ...
Steve's user avatar
  • 451
7 votes
0 answers
166 views

What relations are there between a problem hardness and the hardness of verifying a witness?

I had some hard times trying to formulate the question, so I'll start with some examples: Suppose you are given a Dominating Set instance, $<G,k>$. Now suppose I give you a set of vertices $D$ ...
R B's user avatar
  • 9,458
7 votes
0 answers
207 views

Is the following "Occam's razor" decision problem a member of P?

While thinking about natural language processing, I came up with the following NP problem: OCCAM-k: Given a fixed natural number $k$, consider the following input: a natural number of states $S$ in ...
user avatar
7 votes
0 answers
637 views

Narrowing the gap between BPP and RP

We do not know yet whether the 2-sided error of $BPP$ allows more computing power than the one sided error of $RP$. In view of derandomization results, the conjectured answer is no, since both classes ...
Andras Farago's user avatar
7 votes
0 answers
233 views

Complexity class that captures linear or nearly-linear functions

A particular model I am working with can only compute a function $f: \{0,1\}^n \rightarrow \{0,1\}$ iff $f(x_1,...,x_n)$ is a linear combination (over $\text{GF}(2)$) of the $x_i$'s or has at most a ...
Artem Kaznatcheev's user avatar
6 votes
0 answers
159 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 ...
user68775's user avatar
6 votes
0 answers
127 views

Counting on grid graphs

Are there problems defined on graphs, such as counting 2-factors, Hamiltonian cycles, connected spanning subgraphs etc., that are in $\#P$ and remain hard for grid graphs? Since there seem to be ...
delete000's user avatar
  • 828
6 votes
0 answers
136 views

Is there an analogue of QMA where Merlin gives Arthur unitaries rather than states?

$\def\braket#1#2{\langle#1|#2\rangle}\def\bra#1{\langle#1|}\def\ket#1{|#1\rangle}$Is there an analogue to $\mathsf{QMA}$ where Merlin provides to Arthur single-use access to a unitary operator $U$? By ...
bean's user avatar
  • 161
6 votes
0 answers
249 views

Complexity Class Equalities on the Edge of Inconsistency

What are some of the most extreme potential equalities between computational complexity classes (especially if there is a barrier to refuting them)? These may give us an opportunity to prove better ...
Dmytro Taranovsky's user avatar
6 votes
0 answers
99 views

Is the class NSC closed under complement?

The class $\mathsf{NSC}$ is defined as $\bigcup_{k\in\mathbb{N}}\mathsf{NSC}^k$, where $\mathsf{NSC}^k = \mathsf{NTIMESPACE}[\mathsf{poly},\mathsf{log}^k]$. In a 1991 paper Mix Barrington and McKenzie ...
funnyhow0x3f's user avatar
6 votes
0 answers
293 views

Quantum computer versus Random 3-SAT?

It seems to be commonly believed that a quantum computer cannot efficiently solve NP-hard problems. What about problems that are challenging in the average-case, such as Planted Clique and Random 3-...
Minkov's user avatar
  • 852
6 votes
0 answers
427 views

PSPACE completeness, with different kinds of reductions

PSPACE-complete$_{FP}$ problems are the PSPACE problems such that every other PSPACE problem can be transformed to it with a polynomial time reduction, i.e. the reduction is an algorithm $\in$ FP. ...
François's user avatar
  • 161
6 votes
0 answers
186 views

Complexity of coloring in weakly perfect graphs?

A graph is weakly perfect if the clique number equals the chromatic number, i.e. $\omega(G)=\chi(G)$. Deciding membership is NP-complete according to the paper. Because of the inequality $\omega(G) \...
joro's user avatar
  • 1,955
6 votes
0 answers
233 views

Physical Proof for P versus BPP

Lipton asks for a physical proof of $P\neq NP$. Can we even ask for a physical proof for understanding $P=BPP$ or $P\neq BPP$? Is there anything in physics that lets us avoid randomness? ...
Turbo's user avatar
  • 12.9k
5 votes
0 answers
264 views

What's wrong with this $P \neq BPP$ proof?

I developed this simple argument while learning about the $BP$ operator and McCreight and Meyer's Union Theorem, however I cannot pinpoint where my error is. By the Union Theorem, there exists a total ...
trillianhaze's user avatar
5 votes
0 answers
132 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 ...
Michael Lampis'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