# Questions tagged [complexity-classes]

Computational complexity classes and their relations

596 questions
Filter by
Sorted by
Tagged with
0answers
90 views

### Permanent in Bounded error Quasi Poly time

Is there any consequence to complexity theory if Permanent has a BQP (classical quasipoly version of BPP)? Is there any consequence to complexity theory if Permanent has a QP (classical quasipoly ...
1answer
277 views

### Non-uniform version for the whole polynomial hierarchy

The non-uniform versions of P, NP and coNP are P/poly, NP/poly and coNP/poly. Similarly, we can define a non-uniform version for each level in the PH. For example: $\Sigma_2$/poly consists of ...
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 ...
0answers
70 views

### Is there a relationship between the probabilistic interepretation of Sherali-Adams SDP hierarchy and the Lasserre SDP hierarchy?

Firstly note this paper http://ttic.uchicago.edu/~madhurt/Papers/reductions.pdf where a Lasserre SDP is being setup for the independent set probblem at the bottom of page 4 where the author says says, ...
1answer
149 views

### Why are these two definitions of PLS equivalent?

In the definition of the complexity class $\textsf{PLS}$ we have an algorithm for improving the solutions locally. I have come across the following two definition of such an algorithm. there is a ...
1answer
791 views

### 2-NEXPTIME-complete problems

We have a problem and we found an algorithm that appear to be 2-nexptime. I would like to find known 2-nexptime-complete problems in order to find a lower bound. I found in literature mainly two ...
1answer
160 views

### Is the difference of two languages in NP-complete an NP-complete too? [closed]

Given two languages $L_{1} \in NP$ and $L_{2} \in \textit{NP-complete}$ such that $L_{1} \cup L_{2} \in \textit{NP-complete}$, Is $L_{1}$ in $\textit{NP-complete}$ too?
0answers
202 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 ...
0answers
262 views

### The relation between RP, BPP and NP [duplicate]

I have the following thoughts so I'd like to hear are there any straightforward implications which might support or undermine them. You have a class BPP where problems have a TM with bounded two side ...
1answer
194 views

0answers
148 views

1answer
455 views

### Is there a problem currently known to be outside class $\mathsf{NP}\cup\mathsf{coNP}$ but inside $\mathsf{BPP}$?

May be this is trivial but I do not know the answer. As far as we know $$\mathsf{BPP}\subseteq\mathsf{\Sigma}_2\cap\mathsf{\Pi}_2$$ holds. As far as we know \mathsf{NP}\cup\mathsf{coNP}\subseteq\...
2answers
204 views

### Popular average-case complexity assumptions

Except for planted clique and random 3SAT, what are the other commonly used average-case complexity assumptions?
1answer
971 views

### Intersection of languages in NP

Can intersection of two languages in NP which are not NP complete be NP complete? Can intersection of two languages in coNP which are not coNP complete be coNP complete? Can intersection of two ...
2answers
372 views

1answer
762 views

### “Almost easy” NP-complete problems

Let us say that a language $L$ is P-density-close if there is a polynomial time algorithm that correctly decides $L$ on almost all inputs. In other words, there is an $A\in$ P, such that $L\Delta A$...
7answers
2k views

### Is there a natural problem in quasi-polynomial time, but not in polynomial time?

László Babai recently proved that the Graph Isomorphism problem is in quasipolynomial time. See also his talk at University of Chicago, note from the talks by Jeremy Kun GLL post 1, GLL post 2, GLL ...
1answer
411 views

### Are there more polynomial time problems with complexity lower bounds?

I'm looking for more problems in $P$ with classical time complexity lower bounds. Some people might wonder how you could prove such a lower bound. See below. Exponential Lower Bounds: Claim: If ...
2answers
467 views

### Potentially equal complexity classes without known contradictory relativizations

What are some examples of pairs of complexity classes $A$ and $B$ such that we do not know whether $A=B$, and we do not know contradictory relativizations either (i.e., we do not know oracles $P$ and ...
1answer
285 views

### Two DFA intersection emptiness connections to SETH & L vs P

(re "fine grained complexity") Wehar has proved that Two DFA intersection emptiness in $O(n^{2-\epsilon})$ time → SETH false. does anyone see any particular key proof difficulty, challenge, ...
0answers
119 views

### Complexity classes for problems that can be solved only from the length of the input

A tally language is a language on an alphabet with only one symbol. One can define complexity classes for tally languages, such as $P_1$ (the tally languages that can be decided in polynomial time). ...
0answers
220 views

### Is $\mathsf{NP}$ in $\mathsf{NNC}^1$?

Theorem 2.2 in "Nondeterministic circuits, space complexity and quasigroups", by Wolf, 1994 (a technical report version is available here without fee), proves that NP = NNC, where NNC is the class of ...