complexityClassRelation
P62369
predicate
Indicates a relationship between two computational complexity classes, such as inclusion, equivalence, or separation, within the hierarchy of complexity theory.
Observed surface forms (6)
- complexityClassContext ×5
- equatesComplexityClass ×2
- involvesComplexityClass ×2
- complexityOf3SAT ×1
- relationToZPP ×1
- relationshipStatusWithPSPACE ×1
Sample triples (16)
| Subject | Object |
|---|---|
| Blum–Blum–Shub pseudorandom number generator | security reducible to factoring problem ⓘ |
|
complexity class EXPTIME
surface form:
EXPTIME
|
PSPACE vs EXPTIME is open via predicate surface "relationshipStatusWithPSPACE" ⓘ |
| Furst–Saxe–Sipser lower bounds | AC⁰ via predicate surface "complexityClassContext" NERFINISHED ⓘ |
| Furst–Saxe–Sipser lower bounds | P via predicate surface "complexityClassContext" NERFINISHED ⓘ |
|
Karp reductions
surface form:
Karp reduction
|
NP via predicate surface "complexityClassContext" NERFINISHED ⓘ |
|
Karp reductions
surface form:
Karp reduction
|
NP-complete via predicate surface "complexityClassContext" ⓘ |
|
Karp reductions
surface form:
Karp reduction
|
P via predicate surface "complexityClassContext" ⓘ |
|
MIP equals NEXP
surface form:
MIP = NEXP
|
class of problems solvable by multi-prover interactive proofs via predicate surface "equatesComplexityClass" ⓘ |
|
MIP equals NEXP
surface form:
MIP = NEXP
|
class of problems solvable in nondeterministic exponential time via predicate surface "equatesComplexityClass" ⓘ |
| P versus NP problem | NP via predicate surface "involvesComplexityClass" ⓘ |
| P versus NP problem | P via predicate surface "involvesComplexityClass" ⓘ |
|
complexity class RP
surface form:
RP
|
ZPP equals RP ∩ coRP via predicate surface "relationToZPP" ⓘ |
| SAT problem | NP-complete via predicate surface "complexityOf3SAT" ⓘ |
| Undirected connectivity in log-space | L = SL ⓘ |
| Undirected connectivity in log-space | L ⊆ SL ⓘ |
| Undirected connectivity in log-space | SL ⊆ L ⓘ |