Search Results

Like the Boolean Formula Isomorphism problem, the Group Equations Isomorphism problem is $\mathsf{coNP}$-hard and in $\mathsf{\Sigma_2P}$, for any fixed non-abelian group. See The Complexity of Equiva …

I have two optimization problems, both of whose inputs are from the set $I$ and whose solutions are from the set $S$, one a minimization with objective function $m_{\min}$ and one a maximization with …

In the 2012 paper On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs, the authors state the following (paraphrased from page 11). Theorem 1 (informal). There is a PCP syste …

What is the relationship between $\mathsf{PLS}$ and $\mathsf{APX}$? In other words, are problems that admit a polynomial time local search approximable? Do approximable optimization problems imply a l …

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 …

This is not an answer to your exact question, but perhaps you may find this helpful. You might have a slightly easier time finding results for the class of languages decided by nondeterministic $\mat …

This is a partial answer; maybe it will inspire someone else to provide a better one. $\newcommand{\EBPP}{\mathsf{EBPP}}$ $\newcommand{\CP}{\mathsf{C}_=\mathsf{P}}$ Your class $\EBPP$ is a special ca …

The $\mathsf{P}$-complete problems can be considered "inherently sequential". $\mathsf{P}$-completeness may be defined using either $\mathsf{NC}$ reductions or $\mathsf{L}$ reductions. Since $\mathsf …

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 …

Let $\mathsf{ATISP}(f(n), g(n))$ be the class of languages decided by alternating Turing machines that halt in time $f(n)$ using space $g(n)$. Let $\mathsf{AALTSP}(f(n), g(n))$ be the class of languag …

In Section 3.2 of On Syntactic versus Computational Views on Approximability by Khanna, et al., the authors state that an adaptation of the results from Proof Verification and Hardness of Approximatio …

What do you call the problem of finding a largest possible subset of strings with smallest possible information content? I'm studying a particular instantiation of this problem in a different setting …

This is related to the question Is the Witness Size of Membership for Every NP Language Already Known? Some natural $\mathsf{NP}$(-complete) problems have linear length witnesses: a satisfying assign …

Suppose $n = p^k$ for some prime number $p$ and some non-negative integer $k$. What is (the best-known upper bound on) the complexity of computing $k$ on input $n$ (given in binary)? It is important t …

$ \newcommand{\DSPACE}{\mathsf{DSPACE}} \newcommand{\L}{\mathsf{L}} \newcommand{\P}{\mathsf{P}} \newcommand{\DTIME}{\mathsf{DTIME}} $ $\L^2 \subseteq \P$ would refute the Exponential Time Hypothesis. …