Statements (22)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
theoretical computer science
NP-complete problem |
| gptkbp:alsoKnownAs |
gptkb:X3C
|
| gptkbp:category |
gptkb:mathematics
combinatorial optimization theoretical computer science |
| 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 with |X| = 3q |
| gptkbp:NP-complete |
true
|
| gptkbp:NP-completenessProvedBy |
gptkb:Richard_M._Karp
|
| gptkbp:NP-completenessProvedIn |
1972
|
| gptkbp:reduces |
gptkb:3-dimensional_matching
|
| gptkbp:relatedTo |
gptkb:Steiner_system
hitting set problem set cover problem |
| gptkbp:type |
Does C contain an exact cover for X?
|
| gptkbp:usedIn |
theory of NP-completeness
|
| gptkbp:bfsParent |
gptkb:NP_languages
|
| gptkbp:bfsLayer |
6
|