Распознавание последовательностей со всеми перестановками

25

Для любого n>0 я говорю, что последовательность целых чисел в является -полной, если для каждой перестановки из , записанная как последовательность попарно различных целых чисел , последовательность является подпоследовательностью , т. е. существуеттакой, что для всех .{ 1 , , n } n p { 1 , , n } p 1 , , p n p s 1 i 1 < i 2 < < i n| с | s i j = p j 1 j ns{1,,n}np{1,,n}p1,,pnps1i1<i2<<in|s|sij=pj1jn

Какова сложность следующей проблемы? Это в PTIME или coNP-hard? Обратите внимание, что это в coNP, так как вы можете угадать недостающую последовательность (спасибо @MarzioDeBiasi).

Входные данные : целое число, последовательностьцелых чисел в \ {1, \ ldots, N \} Вывод: это ы п -полным?s { 1 , , n }ns{1,,n}
нs n

Понятие n -полной последовательности известно в комбинаторике, потому что люди исследовали, какова длина самой короткой n -последовательной последовательности как функция от n (см., Например, этот поток mathoverflow для краткого изложения). Однако я не смог найти ссылки на сложность их распознавания. Обратите внимание, что, в частности, мы можем легко построить n -полные последовательности полинома длины по n , а именно, длины n2 , поскольку (1,,n) повторяются n раз (любая перестановка p может быть реализована с помощью выбирая pi в i-ый блок). Следовательно, мы не можем позволить себе вообще перечислять все перестановки.

a3nm
источник
10
Проблема в coNP, потому что пропущенная перестановка p1...pn из строки s может быть проверена за полиномиальное время. Таким образом, проблема может быть завершена coNP
Марцио Де Биаси
@MarzioDeBiasi: верно, это было небрежно, я отредактировал соответственно. Благодарность!
3

Ответы:

13

Я считаю, что проблема полностью завершена. Я загрузил его как препринт arXiv .

Przemysław Uznański
источник
2
Я подробно рассмотрел это доказательство и подтверждаю, что оно мне кажется правильным. Большое спасибо!
a3nm
2
Его версия arXiv вышла в свет
Тайсон Уильямс,