wu :: forums
wu :: forums - NPC: Carpenter's Rule

Welcome, Guest. Please Login or Register.
May 19th, 2019, 9:39pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
(Moderators: Icarus, Eigenray, william wu, SMQ, Grimbal, towr, ThudnBlunder)
   NPC: Carpenter's Rule
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: NPC: Carpenter's Rule  (Read 3748 times)
william wu
wu::riddles Administrator


Gender: male
Posts: 1291
NPC: Carpenter's Rule  
« on: Jun 14th, 2003, 11:36am »
Quote Quote Modify 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


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

mmmmm NP-completeness  Grin
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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board