Exact Cover by 3-Sets (X3C)

GPTKB entity

Statements (22)
Predicate Object
gptkbp:instanceOf theoretical computer science
NP-complete problem
gptkbp:abbreviation gptkb:X3C
gptkbp:category combinatorial problem
covering problem
gptkbp:complexity NP-complete
gptkbp:definedIn Given a set X with 3q elements and a collection C of 3-element subsets of X, does C contain an exact cover for X?
gptkbp:field theoretical computer science
https://www.w3.org/2000/01/rdf-schema#label Exact Cover by 3-Sets (X3C)
gptkbp:input collection C of 3-element subsets of X
finite set X
gptkbp:introduced gptkb:Richard_M._Karp
gptkb:Karp's_21_NP-complete_problems
1972
gptkbp:output yes/no
gptkbp:relatedTo gptkb:3-dimensional_matching
set cover problem
gptkbp:solution_type subset selection
gptkbp:type Does C contain a subcollection that partitions X?
gptkbp:used_in complexity reductions
gptkbp:bfsParent gptkb:Exact_Set_Cover
gptkbp:bfsLayer 7