wu :: forums - Print Page


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

        riddles >> cs >> NPC: Carpenter's Rule
        
(Message started by: william wu on Jun 14^th, 2003, 11:36am)

Title: NPC: Carpenter's Rule
Post by william wu on Jun 14^th, 2003, 11:36am

A cute and relatively simple np-completeness reduction problem:

NPC: Carpenter's Rule

The Carpenter's rule problem, CRULE, is defined as follows:

Instance: A ruler consisting of a sequence of segments of integer lengths L₁, L₂, ... , L_N, with a hinge between each pair of segments, and an integer box length b.

Question: Can the ruler be folded at its hinges so that it fits into the box?

Example ruler; the black stripes represent hinges:

http://www.ocf.berkeley.edu/~wwu/images/riddles/carpenterRule.gif

By reduction from the PARTITION problem, prove that CRULE is NP-complete. (Remember to show that CRULE is in NP.)

Note: The PARTITION problem is defined as follows:

Instance: A set of positive integers s₁, s₂, ... , s_N whose sum S is an even number.

Question: Is their a subset A of the numbers whose sum is exactly S/2?

Title: Re: NPC: Carpenter's Rule
Post by xlh on Jun 24^th, 2003, 9:24pm

mmmmm NP-completeness ;D

Given the partition problem S1 + .. + Sn = S:
Create a ruler with segments 2*S,S, S1,S2,...,Sn,S,2*S and a box of size 2S. If the ruler fits in the box then the first and last segments must stretch the length of the box, and thus the 2nd and 2nd to last segements both must stretch from one side where they meet the 1st/last segements to the exact middle. If there is a partition, then folding the ruler so folding the ruler so that a segement heads left if its in one partition and right if its in the other yields a solution. Conversely if there is a folding that fits in the box then we have a partition defined by the direction of the corresponding segments. So, ruler folding is NP-hard.

We can verify that a folding is correct in polytime so the probem is in NP and thus NP-complete.