Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [complexity-classes]

Computational complexity classes and their relations

29
votes
0answers
872 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\...
27
votes
0answers
612 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". ...
20
votes
0answers
479 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
254 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))$?
18
votes
0answers
358 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
413 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
416 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 ...
16
votes
0answers
265 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
331 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
412 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
210 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 ...
14
votes
0answers
445 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 ...
13
votes
0answers
350 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
471 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
342 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} \...
10
votes
0answers
104 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 ...
9
votes
0answers
100 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
0answers
181 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 ...
8
votes
0answers
112 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 $...
8
votes
0answers
116 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$ ...
8
votes
0answers
307 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
624 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
153 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 ...
7
votes
0answers
84 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 ...
7
votes
0answers
278 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
163 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
509 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
177 views

The power of randomized logspace with two-way access to the random tape

Let $\mathsf{ZPL}$/$\mathsf{RL}$/$\mathsf{BPL}$ denote the classes of the languages which are accepted (with zero/one-side/two-side error) by a logspace Turing machine with one-way access to the ...
7
votes
0answers
227 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
173 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 ...
6
votes
0answers
131 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
156 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
367 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 ...
6
votes
0answers
217 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
165 views

Find a pair of nodes with maximum sum of distances in k given trees

For k edge-weighted trees $T_1,T_2...T_k$ which contain the same set of nodes $\{1,2,... n \}$, I want to find a pair of nodes $(x,y)$ which maxifies $$\sum_{i=1}^k d_i(x,y)$$ where $d_i(x,y)$ ...
5
votes
0answers
187 views

Circuit complexity class of polynomial factoring and Hensel lifting in Zassenhaus' algorithm?

Given a primitive polynomial (gcd of coefficients is $1$) in $\Bbb Z[x]$ we have a polynomial time factoring algorithm for this that runs in time polynomial in degree $d$ and number of bits in ...
5
votes
0answers
123 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
310 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
204 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
257 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
285 views

What happens when PSPACE contains NEXP?

The complexity class NEXP is defined as the set of all languages that an arbitrary nondeterministic exponential time Turing Machine accepts (i.e. NTIME($2^{p(n)}$) for $p()$ a polynomial). In the ...
4
votes
0answers
162 views

Is there a language in NSPACE(O(n)) and (very likely) not in DSPACE(O(n))?

Actually I found that the set of context-sensitive Languages, $\mathbf{CSL}$ ($\mathbf{=NSPACE}(O(n))$ $= \mathbf{LBA}$ accepted languages) are not so widely discussed as $\mathbf{REG}$ (regular ...
4
votes
0answers
85 views

A succinct version of permanent that is $EXP$-complete

Succinct version of permanent is $NEXP$-hard (https://eccc.weizmann.ac.il/report/2012/086/) and so unlikely to be $EXP$-complete. Permanent mod $2$ is in $\oplus L$ and so succinct version is ...
4
votes
0answers
142 views

On status of Valiant's $NC^2=P^{\#P}$ provability program?

In here it is written 'A most interesting/controversial talk was by Leslie Valiant. He explored paths to try to prove that $NC^2=P^{\#P}\dots$'.... This was a decade back. What is the rationale (at ...
4
votes
0answers
71 views

Non-trivial PCP characterizations of complexity classes beyond ELEMENTARY?

There are interesting results of the form $PCP[a(n), b(n)] = \texttt{SOMECLASS(n)}$ for multiple classes in the exponential hierarchy: the most famous one is probably $PCP[O(log(n)), O(1)] = NP$. Are ...
4
votes
0answers
173 views

Subexponential algorithms vs separations

Williams (see also slide 29 here) has shown that an $\frac{2^{n}}{n^{10}}$ algorithm for satisfiability of circuits belonging to a class $\mathcal{C}$ imply that $\mathrm{NEXP}\nsubseteq \mathcal{C}$. ...
4
votes
0answers
120 views

Is there a certificate definition for polyL?

Arora explained in his book a certificate definition for $\mathsf{NL}$ using a read-once tape. Can we apply a similar definition for the class $\mathsf{polyL}$?
4
votes
0answers
238 views

Is there a reason we haven't been able to prove that the existence of natural NPI problems even conditionally under assumption NPI is not empty?

We can write ${\mathsf {NP}}-{\mathsf P}= {\mathsf {NPC}}\cup {\mathsf {NPI}}$ where ${\mathsf {NPC}}$ is the set of ${\mathsf {NP}}$-complete languages (not in ${\mathsf {P}}$ by this partition), ...
4
votes
0answers
170 views

What do we know about $\text{P}^\text{NE}$

I have a $\text{NEXP}$-hard problem, that can be solved by a $\text{NEXP}^\text{NP}$ algorithm using a single oracle call. So from Hemaspaandra we know it is in $\text{P}^\text{NE}$, giving us $\text{...