wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> PUNCHOUT CARDS
        
(Message started by: AlexH on Aug 13^th, 2002, 3:03am)

Title: PUNCHOUT CARDS
Post by AlexH on Aug 13^th, 2002, 3:03am

Thats a big hint :o

[hide]
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).
[/hide]

Title: Re: PUNCHOUT CARDS
Post by william wu on Aug 13^th, 2002, 9:41am

alright, i killed the hint now :)

Title: Re: PUNCHOUT CARDS
Post by AlexH on Aug 13^th, 2002, 12:54pm

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.