complexityClassRelation

P62369
predicate

Indicates a relationship between two computational complexity classes, such as inclusion, equivalence, or separation, within the hierarchy of complexity theory.

Try in SPARQL

All labels observed (7)

Label Occurrences
complexityClassContext 5
complexityClassRelation canonical 4
equatesComplexityClass 2

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 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" ⓘ
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 reductions
surface form: Karp reduction
P via predicate surface "complexityClassContext" ⓘ
Karp reductions
surface form: Karp reduction
NP via predicate surface "complexityClassContext" NERFINISHED ⓘ
Karp reductions
surface form: Karp reduction
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 ⓘ
complexity class EXPTIME
surface form: EXPTIME
PSPACE vs EXPTIME is open via predicate surface "relationshipStatusWithPSPACE" ⓘ
complexity class RP
surface form: RP
ZPP equals RP ∩ coRP via predicate surface "relationToZPP" ⓘ