computationalClass

P29141
predicate

Indicates that two entities share the same computational complexity class or that one entity is categorized within a specified computational complexity class.

Try in SPARQL

All labels observed (8)

Label Occurrences
hasComplexityClass 3
computationalProblem 2
complexityClassInvolved 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: computationalClass
Generated description
Indicates that two entities share the same computational complexity class or that one entity is categorized within a specified computational complexity class.

Sample triples (11)

Subject Object
Game of Life Turing complete ⓘ
Halting problem not decidable in any classical time or space complexity class via predicate surface "hasComplexityClass" ⓘ
Kolmogorov complexity upper semicomputable via predicate surface "semiComputableProperty" ⓘ
The Complexity of Theorem-Proving Procedures
linked to: "The Complexity of Theorem-Proving Procedures"
NP via predicate surface "studiesComplexityClass" ⓘ
Deutsch–Jozsa algorithm O(2^n) via predicate surface "complexityClassicalDeterministic" ⓘ
Cook–Levin theorem NP via predicate surface "complexityClassInvolved" ⓘ
Othello (board game) PSPACE-complete (generalized version) via predicate surface "computerComplexityClass" ⓘ
Reversi PSPACE-complete for generalized versions via predicate surface "hasComplexityClass" ⓘ
Kemeny–Young method Kemeny score computation is NP-hard via predicate surface "computationalProblem" ⓘ
Kemeny–Young method winner determination is NP-hard via predicate surface "computationalProblem" ⓘ
Tic-Tac-Toe very low via predicate surface "hasComplexityClass" ⓘ