Author |
Topic: NPC: Carpenter's Rule (Read 4635 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
NPC: Carpenter's Rule
« on: Jun 14th, 2003, 11:36am » |
 Quote  Modify
|
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 L1, L2, ... , LN, 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 NP-complete. (Remember to show that CRULE is in NP.)
Note: The PARTITION problem is defined as follows:
Instance: A set of positive integers s1, s2, ... , sN 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 14th, 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 24th, 2003, 9:24pm » |
Quote Modify
 Remove
|
mmmmm NP-completeness 
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print