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

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

Разностная последовательность перестановки чисел формируется путем нахождения разности между каждыми двумя соседними числами в перестановке . Другими словами, $a_1, a_2, \ldots a_n$ $\pi$ $1, 2, \ldots n+1$ $\pi$ $a_i= |\pi(i+1)-\pi(i)|$ за $1 \le i \le n$

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

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

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

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

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

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

cc.complexity-theory co.combinatorics np-hardness permutations Мухаммед Аль-Туркистани
источник

Возможно, еще один тривиальный (но более здравый?) Комментарий состоит в том, что если является перестановкой (все значения различны), то проблема состоит в том, чтобы убедиться, что последовательность является изящной маркировкой строки узел, разрешимый за полиномиальное время.

a_{i}

$a_i$

[1.. n]

$[1..n]$

n + 1

$n+1$

Марцио де Биаси

@MarzioDeBiasi Думаю, вы разделяете мою страсть к проблемам с перестановками. Я надеюсь, что я придумал простейшую в вычислительном отношении интересную проблему перестановок :)

Мохаммад Аль-Туркистани

:-) ... Я бы скорее сказал, что мой комментарий исходит непосредственно из тех часов, которые я потратил впустую на проблему изящной маркировки деревьев ... однако у меня есть смутное представление о возможном сокращении полной NP-проблемы для вашей проблемы; если мне удастся формализовать это, я отправлю ответ.

Марцио Де Биаси

K = 2 N

$K=2N$

1...2 N

$1...2N$

i_{2 a - 1} - i_{2 a} = A_{i}

$i_{2a−1}−i_{2a}=A_i$

N P

$NP$

Ответы:

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

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

$2$ $1112112111$

 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 \times w$ $a,b$ $|a-b|=kw$ .

$G$

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

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

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

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

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

Марцио де Биаси
источник

Хорошо, я уверен, что это приведет к решению, гаджет выбора определенно осуществим.

Домоторп

@domotorp: я опубликовал это (я опубликую детали выбора / синхронизации в ближайшие дни); возможно, в нем содержится ошибка, которую я не вижу, однако я поставил 1 доллар на то, что все сокращение может быть значительно упрощено :-)

Марцио Де Биаси

@MarzioDeBiasi Хорошая визуализация. Кажется, вы на правильном пути. Не могли бы вы опубликовать свой ответ на MathOverflow, поскольку эта проблема вызывает значительный интерес?

Мухаммед Аль-Туркистани

@MarzioDeBiasi Не могли бы вы опубликовать свой окончательный ответ (формальный) до истечения срока действия награды?

Мухаммед Аль-Туркистани

@ MohammadAl-Turkistany: Я только что вернулся из поездки, я постараюсь оформить (и проверить с CSP) гаджеты в ближайшие дни.

Марцио Де Биаси