gareth_rees: (Default)
[personal profile] gareth_rees

Karp (1972) introduces the name ‘exact cover’ for the following decision problem:

INPUT: Family Sj of subsets of a set ui, i=1,2,…,t

PROPERTY: There is a subfamily ThSj such that the sets Th are disjoint and ∪Th = ∪Sj = ui, i=1,2,…,t

(The problem being to determine, for an arbitrary input, whether it possesses the property.) Karp goes on to prove that this problem is NP-complete, using a reduction from chromatic number, which has a reduction from satisfiability with at most three literals per clause, which in turn has a reduction from satisfiability, which he proves is NP-complete directly.

Instances of this problem often arise in the solution of combinatorial problems … )

Profile

gareth_rees: (Default)
gareth_rees

December 2015

S M T W T F S
  12345
6789101112
13 141516171819
20212223242526
2728293031  

Style Credit

Expand Cut Tags

No cut tags
Page generated Jul. 24th, 2017 10:31 am
Powered by Dreamwidth Studios