Author |
Topic: PUNCHOUT CARDS (Read 2204 times) |
|
AlexH
Full Member
Posts: 156
|
 |
PUNCHOUT CARDS
« on: Aug 13th, 2002, 3:03am » |
 Quote  Modify
|
Thats a big hint 
Make cards with 1 row per clause of a 3-CNF. For each variable x make one card (with white side face up): in the first column cover holes corresponding to clauses containing x, in the second column cover those corresponding to clauses containing ~x. Make one extra card where the entire second column (white side) is covered.
Given some set of cards covering all holes, construct a 3SAT solution as follows. Assume the extra card is white side up, otherwise flip all cards. Now if the card corresponding to variable x is white side up, then set x=true, otherwise set x=false. Each covered hole on the left column corresponds to the satisfaction of one of the clauses by the selected variable/value, since all holes are covered, all clauses are satisfied.
So punchout cards is NP-hard (and complete since its easy to verify a solution).
|
| « Last Edit: Oct 22nd, 2003, 1:40pm by william wu » |
 IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: PUNCHOUT CARDS
« Reply #2 on: Aug 13th, 2002, 12:54pm » |
Quote Modify
|
In fairness it is a lot more fun working out how a reduction works than groping for which reduction to do. In this particular case the structure of the problem does kind of advertise what reduction probably works anyway.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
