NP-трудность

[max(Im)]

Рассмотрим следующую задачу: на входе числа $c_1,\ldots,c_n,$ неотрицательные целые, а на выходе ответ на вопрос о существовании разбиения множества этих чисел на два подмножества таких, что суммы чисел в каждом подмножестве равны $\frac{1}{2}\sum_{i=1}^nc_i.$
Она NP-полная. Используя это, можно доказать, что задача разбиения на 3 (равных по сумме чисел) части так же NP-полная.
Можно ли, используя NP-полноту только этих задач, показать, что задача о том, существует ли в $\{c_1,\ldots,c_n\}$ подмножество $\{c_{i_1},\ldots,c_{i_k}\},$ такое что $\sum_{t=1}^kc_{i_t}=\frac13\sum_{i=1}^nc_i, $ так же NP-полная?

Это возможно сделать на самом деле используя NP-трудность задачи о рюкзаке, но можно ли свести одну из рассмотренных задач к задаче о выделении 1/3 (назовем это так)?

[Cash]

А чем отличается задача

Цитата:

существует ли в $\{c_1,\ldots,c_n\}$ подмножество $\{c_{i_1},\ldots,c_{i_k}\},$ такое что $\sum_{t=1}^kc_{i_t}=\frac13\sum_{i=1}^nc_i, $

от задачи от которой вы хотите отталкиваться

Цитата:

задача разбиения на 3 (равных по сумме чисел) части

?

[max(Im)]

Тем, что в моей задаче необходимо выделить два множества ("массы" 1/3 и 2/3), а в разбиении на 3 части нужно выделить три множества ("масс" 1/3, 1/3 и 1/3).

[VAL]

max(Im) в сообщении #509392 писал(а):

Рассмотрим следующую задачу: на входе числа $c_1,\ldots,c_n,$ неотрицательные целые, а на выходе ответ на вопрос о существовании разбиения множества этих чисел на два подмножества таких, что суммы чисел в каждом подмножестве равны $\frac{1}{2}\sum_{i=1}^nc_i.$
Она NP-полная. Используя это, можно доказать, что задача разбиения на 3 (равных по сумме чисел) части так же NP-полная.
Можно ли, используя NP-полноту только этих задач, показать, что задача о том, существует ли в $\{c_1,\ldots,c_n\}$ подмножество $\{c_{i_1},\ldots,c_{i_k}\},$ такое что $\sum_{t=1}^kc_{i_t}=\frac13\sum_{i=1}^nc_i, $ так же NP-полная?

Это возможно сделать на самом деле используя NP-трудность задачи о рюкзаке, но можно ли свести одну из рассмотренных задач к задаче о выделении 1/3 (назовем это так)?

А зачем Вам задача о разбиении на три подмножества?
Разве Ваша задача (нахождение подмножества с суммой треть от всех) чем-то принципиально отличается от задачи нахождения подмножества с суммой половина от всех?

[max(Im)]

Принципиально может и не отличается.
Просто интересно, можно доказать NP-полноту этой задачи сведением к ней задачи о нахождении подмножества с суммой половина от всех.

То есть пусть мы умеем решать задачу о выделении одной третьей. А нам нужно выделить половину из $c_1,\ldots,c_n.$ Как используя только этот решатель задачи про треть, выделить половину?

Почему говорил о задачи про разбиение на три подмножества: ее NP-трудность как раз так и можно доказать. Действительно, пусть мы умеем разбивать на три части. И рассмотрим задачу о разбиении на два одинаковых по сумме подмножества для множества $c_1,\ldots,c_n.$ Тогда возьмем множество $\{c_1,\ldots,c_n,\frac12\sum_{i=1}^nc_i\}$ и разделим его на три части (что мы умеем делать). Очевидно, что мы тем самым найдем и искомое разбиение. То есть построено полиномиальное сведение.

Вот и вопрос, а как так же сделать с выделением одной трети?