|
gptkbp:instanceOf
|
theoretical computer science
|
|
gptkbp:characterizedBy
|
solvable in polynomial time by nondeterministic Turing machine
verifiable in polynomial time by deterministic Turing machine
|
|
gptkbp:contains
|
gptkb:NP-hard_problems
decision problems
NP-complete problems
P problems
|
|
gptkbp:definedIn
|
theoretical computer science
|
|
gptkbp:example
|
gptkb:Hamiltonian_path_problem
gptkb:Clique_problem
gptkb:Graph_coloring_problem
gptkb:Subset_sum_problem
gptkb:Vertex_cover_problem
Boolean satisfiability problem
|
|
gptkbp:formalDefinition
|
set of decision problems for which a given solution can be verified in polynomial time
|
|
gptkbp:hasOpenQuestion
|
Is P equal to NP?
|
|
gptkbp:hasSubgroup
|
gptkb:P_complexity_class
PSPACE complexity class
|
|
https://www.w3.org/2000/01/rdf-schema#label
|
NP complexity class
|
|
gptkbp:introduced
|
gptkb:Stephen_Cook
|
|
gptkbp:introducedIn
|
1971
|
|
gptkbp:openProblem
|
gptkb:P_vs_NP_problem
|
|
gptkbp:relatedTo
|
gptkb:NP-hard
gptkb:P_complexity_class
NP-complete
co-NP complexity class
|
|
gptkbp:standsFor
|
nondeterministic polynomial time
|
|
gptkbp:symbol
|
NP
|
|
gptkbp:bfsParent
|
gptkb:P_vs_NP_Problem
|
|
gptkbp:bfsLayer
|
6
|