Statements (28)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
theoretical computer science
NP-complete problem |
| gptkbp:alsoKnownAs |
gptkb:X3C
|
| gptkbp:category |
gptkb:Set_theory
mathematical optimization NP-complete problems |
| gptkbp:definedIn |
theoretical computer science
|
| gptkbp:exactCoverDefinition |
A subcollection C' of C such that every element of X occurs in exactly one member of C'
|
| https://www.w3.org/2000/01/rdf-schema#label |
Exact Cover by 3-Sets
|
| gptkbp:input |
collection C of 3-element subsets of X
finite set X |
| gptkbp:NP-complete |
yes
|
| gptkbp:NP-completenessProvedBy |
gptkb:Richard_M._Karp
|
| gptkbp:NP-completenessProvedIn |
1972
|
| gptkbp:reduces |
gptkb:3SAT
gptkb:Sudoku gptkb:Set_Cover polyomino tiling |
| gptkbp:relatedTo |
gptkb:Set_Cover_Problem
Hitting Set Problem Exact Cover Problem |
| gptkbp:subsetSize |
3
|
| gptkbp:type |
Does C contain an exact cover for X?
|
| gptkbp:usedIn |
gptkb:complexity_theory
theoretical computer science algorithm design |
| gptkbp:bfsParent |
gptkb:Reducibility_Among_Combinatorial_Problems_(Karp,_1972)
|
| gptkbp:bfsLayer |
6
|