# Questions tagged [complexity-classes]

Computational complexity classes and their relations

527 questions
86 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 ...
197 views

### variant of Critical SAT

The language Critical SAT is defined as the set of $CNF$ boolean formulas $f$ such that $f \in UNSAT$ but removing any clause from $f$ makes it satisfiable. It is known that Critical SAT is $DP$-...
158 views

### Closure properties of $L$ (DLOGSPACE)? [closed]

What are the closure properties of $L$ (DLOGSPACE)? I'm not only intrested in these properties (if of course $S$ and $T$ are in $L$) : $S \cap T$ $S^*$ (kleene-star) $S.T$ (concat)
182 views

81 views

### A uniform computability model to define time and space complexity (even in the sublinear case) [closed]

To define time complexity the Turing machine model with only one tape (for input, work and output) is used. This TMM is also used to define the $s(n)$-space complexity for $s(n) \ge n$. But if $s(n)$ ...
223 views

### Dp completeness of a problem

Given a Boolean formula $\varphi$ over the variables $\{x_1...x_n\}$ , an assignment $T_0$ for $\varphi$ and an integer $k$, I am interested in the following question: Does $k$ is the minimal number ...
143 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 ...
164 views

72 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 ...
146 views

### Finding a certificate if E=NE

If $\textbf{P}= \textbf{NP}$ then for every language from $\textbf{NP}$ there exists an algorithm of finding a certificate in polynomial time. Assume that $\textbf{E} = \textbf{NE}$. Is it true that ...
149 views

### $NotTooManyP^{cc}$ class in communication complexity

Class $P^{cc}$ is class of languages admitting deterministic communication protocol with polylog bits of communication. Class $NP^{cc}$ is class of languages admitting nondeterministic communication ...
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$ ...
80 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 ...
242 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 ...
87 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 ...
63 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, ...
131 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 ...
486 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 ...
134 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?
193 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 ...
202 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 ...
183 views

262 views

### Is there any good literature on the computational complexity of function problems?

There are some cstheory questions that touches function-problems. Like this: Complexity class corresponding to sorting So here is the question: Is there good literature about the computational ...