wu :: forums « wu :: forums - NPC: Carpenter's Rule » Welcome, Guest. Please Login or Register. Oct 21st, 2018, 3:08am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    cs (Moderators: Eigenray, towr, SMQ, ThudnBlunder, Grimbal, Icarus, william wu)    NPC: Carpenter's Rule « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: NPC: Carpenter's Rule  (Read 3659 times)
william wu

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

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »