Author 
Topic: NPC: Carpenter's Rule (Read 3674 times) 

william wu
wu::riddles Administrator
Gender:
Posts: 1291


NPC: Carpenter's Rule
« on: Jun 14^{th}, 2003, 11:36am » 
Quote Modify

A cute and relatively simple npcompleteness 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_{1}, L_{2}, ... , 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: By reduction from the PARTITION problem, prove that CRULE is NPcomplete. (Remember to show that CRULE is in NP.) Note: The PARTITION problem is defined as follows: Instance: A set of positive integers s_{1}, s_{2}, ... , s_{N} whose sum S is an even number. Question: Is their a subset A of the numbers whose sum is exactly S/2?

« Last Edit: Jun 14^{th}, 2003, 11:41am by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



xlh
Guest


Re: NPC: Carpenter's Rule
« Reply #1 on: Jun 24^{th}, 2003, 9:24pm » 
Quote Modify
Remove

mmmmm NPcompleteness 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 NPhard. We can verify that a folding is correct in polytime so the probem is in NP and thus NPcomplete.


IP Logged 



