decisionProblem

P132452
predicate

Indicates that the subject is a computational problem for which the task is to decide, with a yes/no answer, whether given inputs satisfy a specified condition.

Try in SPARQL

All labels observed (6)

Label Occurrences
hasDecisionProblem 3
decisionProblemType 2
decisionQuestion 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: decisionProblem
Generated description
Indicates that the subject is a computational problem for which the task is to decide, with a yes/no answer, whether given inputs satisfy a specified condition.

Sample triples (10)

Subject Object
Hamiltonian cycle concept
surface form: Hamiltonian cycle
Hamiltonian cycle problem ⓘ
Cook–Levin theorem yes via predicate surface "concernsDecisionProblems" ⓘ
Post correspondence problem existence of a matching sequence of indices via predicate surface "decisionQuestion" ⓘ
complexity class BPP
surface form: BPP
language recognition via predicate surface "decisionProblemType" ⓘ
complexity class RP
surface form: RP
languages over finite alphabets via predicate surface "decisionProblemType" ⓘ
3-SAT is the given 3-CNF formula satisfiable via predicate surface "decisionQuestion" ⓘ
LTL satisfiability via predicate surface "hasDecisionProblem" ⓘ
LTL model checking via predicate surface "hasDecisionProblem" ⓘ
Eulerian digraph testing whether a given digraph is Eulerian via predicate surface "hasDecisionProblem" ⓘ
Eulerian digraph linear time in number of vertices plus edges via predicate surface "decisionProblemComplexity" ⓘ