Можете ли вы определить сумму двух перестановок за полиномиальное время?

29

Были два вопросы недавно спросил о cs.se , которые были либо связанные или имели особый случай , эквивалентный следующему вопросу:

Предположим, у вас есть последовательность из n чисел, такая что n i = 1 a i = n ( n + 1 ) . Разложите его в сумму двух перестановок, π и , из , так что .a1,a2,anni=1nai=n(n+1).πσ1nai=πi+σi

Есть некоторые необходимые условия: если отсортированы так, что , то мы должны иметьaia1a2an

i=1kaik(k+1).

Однако этих условий недостаточно. Из ответа на этот вопрос по математике, который я задал, последовательность 5,5,5,9,9,9 не может быть разложена как сумма двух перестановок (это можно увидеть, используя тот факт, что оба 1 или 5 могут только быть в паре с 4).

Итак, мой вопрос: какова сложность этой проблемы?

Питер Шор
источник
Кстати, мне пришла в голову простая вариация, и я не уверен в ее сложности. Можете ли вы определить свободную сумму с фиксированной точкой двух перестановок за полиномиальное время? (Мы требуем, чтобы две перестановки расходятся в каждой позиции есть для всех I )πiσii
Mohammad Al-Turkistany

Ответы:

20

Нет, вы не можете определить сумму двух перестановок за полиномиальное время, если P = NP. Ваша задача является NP-полной, так как версия решения вашей проблемы эквивалентна NP-полной задаче Числовое сопоставление с целевыми суммами:2

Входные данные: последовательность целых натуральных чисел , n i = 1 a i = n ( n + 1 ) , 1 a i2 n для 1 i na1,a2,ani=1nai=n(n+1)1ai2n1in

Вопрос: Есть ли две перестановки и ψ 2 такие , что ψ 1 ( я ) + ψ 2 ( я ) = а яψ1ψ2ψ1(i)+ψ2(i)=ai для ?1in

В ссылке, строго ограниченный вариант ЧИСЛЕННОГО 3-мерного сопоставления (RN3DM) оказался сильно NP-полным.

RN3DM, Учитывая мультимножеством целых чисел и целого числа e, такого что n j = 1 u j + n ( n + 1 ) = n e , существуют ли две перестановки λ и µ, такие что u j + λ ( j ) +U={u1,...,un}ej=1nuj+n(n+1)=neλμuj+λ(j)+μ(j)=e, Для ?j=1,...,n

Существует простое сокращение от RN3DM до числового сопоставления с проблемой целевых сумм: данный пример RN3DM. Построим соответствующий экземпляр, сделав a i = e - u i для 1 i n2ai=eui1in

В. Ю., Х. Хогевен и Дж. К. Ленстра. Минимизация рабочего времени в поточном цехе с двумя машинами с задержками и операциями в единицу времени - трудная задача . Журнал планирования, 7: 333–348, 2004

РЕДАКТИРОВАТЬ 1 октября . Ваша проблема называется суммирования. С 1998 года он включен в ОТКРЫТЫЕ ПРОБЛЕМЫ КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ Стивом Хедетниеми.

Мухаммед Аль-Туркистани
источник
2
Спасибо за ответ. Я ответил на одну из проблем на cs.se, которая вдохновила эту проблему (которая не была в форме, на которую прямо ответил ваш отзыв), но я думаю, что у вас должна быть первая возможность ответить на вторую, поскольку ответ дан в вашей ссылке.
Питер Шор
Большое спасибо, Питер. Я рад, что смог вам помочь. Я думаю, что вы дадите лучший ответ. Поэтому, пожалуйста, продолжайте и ответьте на этот вопрос тоже.
Мухаммед Аль-Туркистани
Вот формулировка проблемы, как она появилась на приведенной выше веб-странице: СУММЫ ПЕРМУТАЦИИ [Cheston, 198X] INSTANCE: Массив A [1..n] натуральных чисел. ВОПРОС: Существуют ли две перестановки r и s натуральных чисел {1,2, ..., n} такие, что для 1 <= i <= n, r (i) + s (i) = A [i] ?
Мухаммед Аль-Туркистани
4

С другой стороны, Маршалл Холл показал, что можно легко определить разницу двух перестановок.

анонимный лось
источник
14
Теорема Маршалла Холла применима и к сумме, но и разница, и сумма должны быть вычислены по модулю чтобы применить его результат. По Z сумма и разница являются NP-полными. nZ
Питер Шор
3
@PeterShor Для полноты, пожалуйста, оставьте свой комментарий как отдельный ответ, предоставив пробный набросок NP-полноты определения разницы двух перестановок.
Мохаммед Аль-Туркистани
3
Для полноты: предположим, что у нас есть две перестановки и π . Тогда ˉ π ( i ) = n + 1 - π ( i ) также является перестановкой. Теперь, если ϕ + π - мультимножество { x 1 , x 2 , , x n } , то ϕ - ˉ π - мультимножество { x 1 - ( n + 1 ,ϕππ¯(i)=n+1π(i)ϕ+π{x1,x2,,xn}ϕπ¯ . Например, { - 2 , - 2 , - 2 , 2 , 2 , 2 } нельзя представить как разность двух перестановок, поскольку { 5 , 5 , 5 , 9 , 9 , 9 } не является суммой двух перестановок.{x1(n+1),x2(n+1),,xn(n+1)}{2,2,2,2,2,2}{5,5,5,9,9,9}
Питер Шор