Questions tagged [complexity-classes]

Computational complexity classes and their relations

137 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
29
votes
0answers
953 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\...
28
votes
0answers
644 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". ...
21
votes
0answers
621 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 ...
20
votes
0answers
263 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))$?
20
votes
0answers
394 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 ...
17
votes
0answers
464 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-...
16
votes
0answers
293 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, ...
15
votes
0answers
443 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 ...
15
votes
0answers
469 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 ...
15
votes
0answers
337 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}...
14
votes
0answers
454 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, $\...
14
votes
0answers
437 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}$ ...
14
votes
0answers
213 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 ...
13
votes
0answers
360 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 ...
12
votes
0answers
537 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 ...
12
votes
0answers
367 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} \...
11
votes
0answers
309 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 $|...
11
votes
0answers
206 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+\...
11
votes
1answer
512 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? ...
10
votes
0answers
195 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 ...
10
votes
0answers
110 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 ...
10
votes
0answers
202 views

Complexity of unique coloring of graphs

The Isolation lemma of Mulmuley, Vazirani, and Vazirani can be used to show that certain $\mathsf{NP}$-complete problems can be reduced via randomized polytime reductions to the unique solution ...
9
votes
0answers
141 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 $...
9
votes
0answers
114 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 ...
9
votes
1answer
505 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 ...
8
votes
0answers
174 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 ...
8
votes
0answers
121 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 ...
8
votes
0answers
331 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)...
8
votes
0answers
629 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 ...
7
votes
0answers
119 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$ ...
7
votes
0answers
302 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 ...
7
votes
0answers
163 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$ ...
7
votes
0answers
182 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 ...
7
votes
0answers
405 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 ...
7
votes
0answers
577 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 ...
7
votes
0answers
230 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 ...
6
votes
0answers
81 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 ...
6
votes
0answers
167 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 ...
6
votes
0answers
88 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 ...
6
votes
0answers
137 views

Does it matter who begins communication in $IP(f(x))$?

Consider $IP(f(x))$, in other words, the class of languages that admit a private coin protocol $(P, V)$ running in $f(x)$ rounds (often in terms of the size of $x$), satisfying standard constraints. ...
6
votes
0answers
173 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) \...
6
votes
0answers
226 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? ...
5
votes
0answers
120 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 ...
5
votes
0answers
201 views

Does the existence of an RP-complete language imply P = RP?

(I'm not sure if this is research-level, but I couldn't find an answer to this question elsewhere) The question of whether there exists an RP-complete language seems to be open, but I guess we believe ...
5
votes
0answers
143 views

An oracle in $\mathsf{NEXP}$ that separates ZPP from BPP

Does there exist an oracle $A \in \mathsf{NEXP}$ such that $ \mathsf{ZPP}^A \neq \mathsf{BPP}^A$?
5
votes
0answers
339 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. ...
5
votes
0answers
211 views

Is there an online algorithm for solving any P-complete problem?

We can think of the class $NC$ as the class of problems that can be solved in parallel, whereas a $P$-complete problem probably has no parallel solution. My question is: where do online algorithms ...
5
votes
0answers
263 views

Big O notation for “modulo a polynomial”

Is there a notation that would be like the Big O notation (let's say Big P), but with the following definition: $f=P(g)$ if there exists a polynomial p such that for n large enough, $f\leq p(g(n))$? ...
4
votes
0answers
115 views

Why can MIP be restricted to just two provers?

In several places I see it referred to that the MIP class can be assumed to be two interactive provers that don't communicate with each other, rather than any polynomial number of provers. Why are ...
4
votes
0answers
84 views

BPP fragment of a PSPACE complete problem

Consider a PSPACE-complete problem (e.g., TQBF). Is there a sub-problem in BPP, that is not known to be in P? Is there a general technique of finding such sub-problems? Are any of them "natural" (i.e....