Головоломка ножницы

18

Проблема: нам дают набор палочек, имеющих целую длину. Общая сумма их длин n (n + 1) / 2.

Можем ли мы разбить их, чтобы получить палочки размером за полиномиальное время? 1,2,...,N

Удивительно, но единственная ссылка, которую я нахожу для этой проблемы, - это древнее обсуждение:

http://www.iwriteiam.nl/cutsticks.html

Что еще известно о проблеме? Можем ли мы доказать, что проблема «в подвешенном состоянии»?

Обновление: проблема с режущими палками имеет ограничение, что каждая палка имеет длину не менее единиц. (См. Комментарии и ответ Цуёси для случая без ограничений).N

Jagadish
источник
1
Формулировка проблемы в приведенной вами ссылке имеет следующее дополнительное требование, с которым проблема, кажется, имеет больше смысла: «Ни одна из палочек не короче ». N
Юкка Суомела
Это нерешенная проблема, чтобы определить, всегда ли это возможно.
Эмиль
@Emil: у вас есть ссылка? Что-нибудь более недавнее, чем древняя (1995 г.) дискуссия, связанная в ОП?
Юкка Суомела
@Jukka Моя ошибка. Я забыл упомянуть этот момент, так как у меня сложилось впечатление, что проблема не изменится значительно с этим ограничением. В любом случае, я счастлив, так как ответ Цуёси породил интересный вопрос.
Джагадиш
это довольно изящная проблема, но название вводит в заблуждение. Это говорит о том, что это проблема теории сложности, когда на самом деле это крутая головоломка с алгоритмами, такая же, как проблема с перемешиванием. Может быть, вам следует перефразировать заголовок.
Суреш Венкат

Ответы:

16

Предостережение: как Юкка Суомела прокомментировал вопрос, на странице, связанной с вопросом, находится проблема, отличная от проблемы, указанной в вопросе, в том, что проблема на странице имеет ограничение, состоящее в том, что длина данных палочек больше или равна п. Этот ответ о проблеме без этого ограничения. Поскольку комментарий Эмиля по этому вопросу относится к проблеме с ограничением, нет противоречия между его комментарием и следующим ответом.


Проблема является NP-полной, даже если числа даны в одинарных.

3-секционная задача - это следующая проблема:
Экземпляр : положительные целые числа a 1 ,…, a n в унарном, где n = 3m, а сумма n целых чисел равна mB, так что каждое a i удовлетворяет B / 4 < а я <B / 2.
Вопрос : Можно ли разбить целые числа a 1 ,…, a n на m мультимножеств, чтобы сумма каждого мультимножества была равна B?

Задача с 3 разделами является NP-полной, даже если a 1 ,…, a n все различны [HWW08] (спасибо Сержу Гасперсу за то, что он рассказал мне об этом ). Можно ограничить эту ограниченную версию задачи с 3 разделами следующим образом.

Предположим, что нам дан пример задачи с 3 разбиениями, состоящей из различных положительных целых чисел a 1 ,…, a n . Пусть m = n / 3 и B = (a 1 +… + a n ) / m, и пусть N будет максимумом среди a i . Рассмотрим следующий случай с проблемой палки: экземпляр состоит из одной палки длины k для каждого k∈ {1,…, N} ∖ {a 1 ,…, a n } и m палок длины B. Используя факт что каждый a i удовлетворяет a i > B / 4 ≥ N / 2, нетрудно доказать, что эта проблема со стержнем имеет решение тогда и только тогда, когда решение задачи с 3 разбиениями имеет решение.

Ссылки

[HWW08] Хизер Хьюлетт, Тодд Дж. Уилл, Герхард Дж. Вёджингер. Мультиграф реализации последовательностей степеней: максимизация проста, минимизация трудна. Письма об исследовании операций , 36 (5): 594–596, сентябрь 2008 г. http://dx.doi.org/10.1016/j.orl.2008.05.004

Цуёси Ито
источник
3
Я не знаю, если проблема с 3 разделами остается NP-полной или нет, если числа различны, и я спрашиваю об этом: cstheory.stackexchange.com/questions/716/…
Tsuyoshi Ito
Серж Гаспер сказал мне, что это так (спасибо!). Я упростил доказательство, используя его.
Цуёси Ито