Questions tagged [complexity-classes]
Computational complexity classes and their relations
192
questions with no upvoted or accepted answers
30
votes
0
answers
779
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".
...
- 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\...
22
votes
0
answers
773
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 ...
- 5,273
21
votes
0
answers
277
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))$?
- 21.5k
20
votes
0
answers
478
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 ...
- 2,281
17
votes
0
answers
378
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, ...
- 8,598
17
votes
0
answers
506
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-...
- 5,273
15
votes
0
answers
487
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 ...
- 2,537
15
votes
0
answers
511
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 ...
- 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}...
- 16.5k
14
votes
0
answers
469
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, $\...
- 5,127
14
votes
0
answers
518
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}$ ...
- 141
14
votes
0
answers
231
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 ...
- 803
12
votes
0
answers
355
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 ...
- 121
12
votes
0
answers
673
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 ...
- 793
12
votes
0
answers
403
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} \...
- 1,261
12
votes
0
answers
373
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 ...
- 3,664
11
votes
0
answers
339
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 $|...
- 1,973
11
votes
0
answers
268
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+\...
- 219
11
votes
1
answer
606
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? ...
- 2,579
10
votes
0
answers
224
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 ...
- 1,973
10
votes
0
answers
182
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 ...
- 429
9
votes
0
answers
182
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 $...
- 2,537
9
votes
0
answers
141
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 ...
- 223
9
votes
0
answers
515
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 ...
- 20.8k
9
votes
1
answer
576
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 ...
- 1,596
8
votes
0
answers
367
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 ...
- 12.8k
8
votes
0
answers
146
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 ...
- 383
8
votes
0
answers
348
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)...
- 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 ...
- 119
7
votes
0
answers
188
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. ...
- 1,181
7
votes
0
answers
171
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 ...
- 273
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$ ...
- 1,973
7
votes
0
answers
316
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 ...
- 451
7
votes
0
answers
165
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$ ...
- 9,438
7
votes
0
answers
205
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 ...
user1338
7
votes
0
answers
635
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 ...
- 11.3k
7
votes
0
answers
232
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 ...
- 10.2k
6
votes
0
answers
152
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 ...
- 61
6
votes
0
answers
122
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 ...
- 778
6
votes
0
answers
134
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 ...
- 161
6
votes
0
answers
240
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 ...
- 2,537
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 ...
- 121
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-...
- 832
6
votes
0
answers
421
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. ...
- 161
6
votes
0
answers
185
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) \...
- 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?
...
- 12.8k
5
votes
0
answers
125
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 ...
- 3,416
5
votes
0
answers
119
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 ...
- 101
5
votes
0
answers
233
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 ...
- 256