|
gptkbp:instanceOf
|
theoretical computer science
|
|
gptkbp:characterizedBy
|
existence of polynomial-time verifiers
nondeterministic polynomial-time Turing machines
|
|
gptkbp:contains
|
gptkb:NP-hard_problems
gptkb:P_(complexity_class)
NP-complete problems
|
|
gptkbp:definedIn
|
decision problems verifiable in polynomial time by a deterministic Turing machine
|
|
gptkbp:example
|
gptkb:Hamiltonian_path_problem
gptkb:Clique_problem
gptkb:Graph_coloring_problem
gptkb:Subset_sum_problem
gptkb:Vertex_cover_problem
gptkb:Boolean_satisfiability_problem_(SAT)
|
|
gptkbp:field
|
theoretical computer science
|
|
gptkbp:hasCompleteProblems
|
NP-complete
|
|
gptkbp:hasHardProblems
|
gptkb:NP-hard
|
|
gptkbp:hasProperty
|
closed under concatenation
closed under Kleene star
closed under homomorphism
closed under intersection
closed under inverse homomorphism
closed under polynomial-time many-one reductions
closed under reversal
closed under union
not known to be closed under complement
|
|
gptkbp:hasSubgroup
|
gptkb:P_(complexity_class)
gptkb:PSPACE_(complexity_class)
|
|
https://www.w3.org/2000/01/rdf-schema#label
|
NP (complexity class)
|
|
gptkbp:introduced
|
gptkb:Stephen_Cook
gptkb:Leonid_Levin
|
|
gptkbp:introducedIn
|
1971
|
|
gptkbp:numberOfIssues
|
Are there NP-intermediate problems?
Does NP = co-NP?
Does P = NP?
Is SAT in P?
Is graph isomorphism in P?
|
|
gptkbp:openQuestion
|
Is P equal to NP?
|
|
gptkbp:relatedTo
|
gptkb:P_vs_NP_problem
gptkb:BPP_(complexity_class)
gptkb:EXP_(complexity_class)
gptkb:FNP_(function_problems)
gptkb:NP-intermediate
gptkb:PH_(polynomial_hierarchy)
gptkb:RP_(complexity_class)
gptkb:ZPP_(complexity_class)
gptkb:co-NP_(complexity_class)
|
|
gptkbp:standsFor
|
nondeterministic polynomial time
|
|
gptkbp:symbol
|
NP
|
|
gptkbp:bfsParent
|
gptkb:P_vs_NP_problem
|
|
gptkbp:bfsLayer
|
5
|