Эффективный алгоритм существования перестановки с последовательностью разностей?

12

Этот вопрос мотивирован этим постом, Можете ли вы определить сумму двух перестановок за полиномиальное время? и мой интерес к вычислительным свойствам перестановок.

Разностная последовательность перестановки чисел формируется путем нахождения разности между каждыми двумя соседними числами в перестановке . Другими словами,a1,a2,an1 , 2 , n + 1 π a i = | π ( i + 1 ) - π ( i ) | 1 i nπ1,2,n+1πai=|π(i+1)π(i)|за1in

Например, последовательность является последовательностью разностей перестановок . При этом последовательности и не являются последовательностями различий любой перестановки чисел .2 3 4 1 2 , 2 , 3 3 , 1 , 2 1 , 2 , 3 , 41,1,323412,2,33,1,21,2,3,4

Существует ли эффективный алгоритм для определения, является ли данная последовательность разностной последовательностью для некоторой перестановки , или это NP-сложный?π

РЕДАКТИРОВАТЬ : Мы получим вычислительно эквивалентную задачу, если мы сформулируем задачу с использованием круговых перестановок.

РЕДАКТИРОВАТЬ 2 : Крест размещен на MathOverflow, Насколько сложно реконструировать перестановку из ее последовательности различий?

РЕДАКТИРОВАТЬ3 Присудить награду за эскиз доказательства, и я приму ответ после получения полного формального доказательства.

РЕДАКТИРОВАТЬ 4 : хорошее доказательство полноты Марцио было опубликовано в электронном журнале комбинаторики .NP

Мухаммед Аль-Туркистани
источник
1
Возможно, еще один тривиальный (но более здравый?) Комментарий состоит в том, что если является перестановкой (все значения различны), то проблема состоит в том, чтобы убедиться, что последовательность является изящной маркировкой строки узел, разрешимый за полиномиальное время. [ 1 .. n ] n + 1ai[1..n]n+1
Марцио де Биаси
2
@MarzioDeBiasi Думаю, вы разделяете мою страсть к проблемам с перестановками. Я надеюсь, что я придумал простейшую в вычислительном отношении интересную проблему перестановок :)
Мохаммад Аль-Туркистани
2
:-) ... Я бы скорее сказал, что мой комментарий исходит непосредственно из тех часов, которые я потратил впустую на проблему изящной маркировки деревьев ... однако у меня есть смутное представление о возможном сокращении полной NP-проблемы для вашей проблемы; если мне удастся формализовать это, я отправлю ответ.
Марцио Де Биаси

Ответы:

10

Это эскиз возможного сокращения, чтобы доказать, что это NP-сложный:

ai...11111... ) (Я называю их 1SEQ) заставляют подпоследовательность увеличения или уменьшения числа в перестановке;

21112112111

 a_i seq.:     1 1 1  2  1 1  2   1  1  1  forces
 permutation: 1 2 3 4 _ 6 7 8 _ 10 11 12 13 (or its decreasing equivalent)
 (from 4 you cannot go back to 2,
 from 8 you cannot go back to 6)

Отверстия должны быть заполнены в остальной части перестановки.

3) используя достаточно большой 1SEQ, за которым следует 1SEQ с некоторыми дырками, а затем еще один большой 1SEQ, вы можете построить принудительную линию ;

4) объединяя множество принудительных линий, вы можете построить график сетки перестановок, в котором узлы соответствуют отсутствующим числам в базовой принудительной перестановке.

Например, последовательность 1111111112111111111112111111111 вызывает следующий график сетки перестановок 5x7:

29 30 31 32 33 34 35
22 23 24    26 27 28
15 16 17 18 19 20 21
 8  9 10    12 13 14   
 1  2  3  4  5  6  7

w×wa,b|ab|=kw .

G

GG ; это требует довольно сложного гаджета - «гаджета выбора», который должен быть создан в другой части графа сетки перестановок;

7) Вы можете заполнить все дыры (т.е. завершить перестановку) тогда и только тогда, когда исходный граф сетки имеет гамильтонов цикл

РЕДАКТИРОВАТЬ: 27 июля 2013

Я попытался формально доказать NP-полноту проблемы: я ввел новую проблему (проблема Crazy Frog ) - NPC. Задача «Перестановочная перестройка из различий» эквивалентна «1-D задаче« Безумная лягушка »без заблокированных ячеек» (которая также является NPC).

Для получения подробной информации о сокращении см. Мой вопрос / ответ по теме «Два варианта гамильтоновых путей» или загрузите черновик доказательства «Когда лягушка встречает перестановку» :)) (я все еще проверяю / дополняю его)

Марцио де Биаси
источник
Хорошо, я уверен, что это приведет к решению, гаджет выбора определенно осуществим.
Домоторп
@domotorp: я опубликовал это (я опубликую детали выбора / синхронизации в ближайшие дни); возможно, в нем содержится ошибка, которую я не вижу, однако я поставил 1 доллар на то, что все сокращение может быть значительно упрощено :-)
Марцио Де Биаси
@MarzioDeBiasi Хорошая визуализация. Кажется, вы на правильном пути. Не могли бы вы опубликовать свой ответ на MathOverflow, поскольку эта проблема вызывает значительный интерес?
Мухаммед Аль-Туркистани
@MarzioDeBiasi Не могли бы вы опубликовать свой окончательный ответ (формальный) до истечения срока действия награды?
Мухаммед Аль-Туркистани
@ MohammadAl-Turkistany: Я только что вернулся из поездки, я постараюсь оформить (и проверить с CSP) гаджеты в ближайшие дни.
Марцио Де Биаси