complexityClassRelation
P62369
predicate
Indicates a relationship between two computational complexity classes, such as inclusion, equivalence, or separation, within the hierarchy of complexity theory.
All labels observed (7)
| Label | Occurrences |
|---|---|
| complexityClassContext | 5 |
| complexityClassRelation canonical | 4 |
| equatesComplexityClass | 2 |
| involvesComplexityClass | 2 |
| complexityOf3SAT | 1 |
| relationToZPP | 1 |
| relationshipStatusWithPSPACE | 1 |
Description generation (PDg)
The one-sentence description above was generated by prompting gpt-5.1 with the predicate name and this instruction.
Instruction
Given a predicate that represents a relationship or action between entities, generate a one-sentence description explaining its meaning. # Instructions Focus on describing the relationship, not the entities themselves. # Response Format Begin the description with \' Indicates...\'
Input
Predicate: complexityClassRelation
Generated description
Indicates a relationship between two computational complexity classes, such as inclusion, equivalence, or separation, within the hierarchy of complexity theory.
Sample triples (16)
| Subject | Object |
|---|---|
| Blum–Blum–Shub pseudorandom number generator | security reducible to factoring problem ⓘ |
| P versus NP problem | P via predicate surface "involvesComplexityClass" ⓘ |
| P versus NP problem | NP via predicate surface "involvesComplexityClass" ⓘ |
|
MIP = NEXP
linked to:
MIP equals NEXP
|
class of problems solvable by multi-prover interactive proofs via predicate surface "equatesComplexityClass" ⓘ |
|
MIP = NEXP
linked to:
MIP equals NEXP
|
class of problems solvable in nondeterministic exponential time via predicate surface "equatesComplexityClass" ⓘ |
| SAT problem | NP-complete via predicate surface "complexityOf3SAT" ⓘ |
| Furst–Saxe–Sipser lower bounds | AC⁰ via predicate surface "complexityClassContext" NERFINISHED ⓘ |
| Furst–Saxe–Sipser lower bounds | P via predicate surface "complexityClassContext" NERFINISHED ⓘ |
|
Karp reduction
linked to:
Karp reductions
|
P via predicate surface "complexityClassContext" ⓘ |
|
Karp reduction
linked to:
Karp reductions
|
NP via predicate surface "complexityClassContext" NERFINISHED ⓘ |
|
Karp reduction
linked to:
Karp reductions
|
NP-complete via predicate surface "complexityClassContext" ⓘ |
| Undirected connectivity in log-space | L = SL ⓘ |
| Undirected connectivity in log-space | SL ⊆ L ⓘ |
| Undirected connectivity in log-space | L ⊆ SL ⓘ |
|
EXPTIME
linked to:
complexity class EXPTIME
|
PSPACE vs EXPTIME is open via predicate surface "relationshipStatusWithPSPACE" ⓘ |
|
RP
linked to:
complexity class RP
|
ZPP equals RP ∩ coRP via predicate surface "relationToZPP" ⓘ |