Search Results
Search type | Search syntax |
---|---|
Tags | [tag] |
Exact | "words here" |
Author |
user:1234 user:me (yours) |
Score |
score:3 (3+) score:0 (none) |
Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
Views | views:250 |
Code | code:"if (foo != bar)" |
Sections |
title:apples body:"apples oranges" |
URL | url:"*.example.com" |
Saves | in:saves |
Status |
closed:yes duplicate:no migrated:no wiki:no |
Types |
is:question is:answer |
Exclude |
-[tag] -apples |
For more details on advanced search visit our help page |
Computational complexity classes and their relations
3
votes
Problems in $\text{PSPACE} \cap \text{Co-NP-Hard}$
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 …
1
vote
0
answers
227
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 …
1
vote
In what class are randomized algorithms that err with exactly 25% chance?
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 …
20
votes
0
answers
488
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 …
10
votes
1
answer
216
views
Can $\log^k n$ alternations be simulated in $\mathsf{NC}^k$?
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 …
26
votes
1
answer
807
views
What is $\mathsf{NP}$ restricted to linear size witnesses?
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 …
28
votes
What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?
$
\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. …
49
votes
4
answers
2k
views
What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?
We know that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P}$ and that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq $ $\mathsf{polyL}$, where $\mathsf{L}^2 = \mathsf{DSPAC …