Для любого я говорю, что последовательность целых чисел в является -полной, если для каждой перестановки из , записанная как последовательность попарно различных целых чисел , последовательность является подпоследовательностью , т. е. существуеттакой, что для всех .{ 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 ≤ n
Какова сложность следующей проблемы? Это в PTIME или coNP-hard? Обратите внимание, что это в coNP, так как вы можете угадать недостающую последовательность (спасибо @MarzioDeBiasi).
Входные данные : целое число, последовательностьцелых чисел в \ {1, \ ldots, N \} Вывод: это ы п -полным?s { 1 , … , n }
н
Понятие -полной последовательности известно в комбинаторике, потому что люди исследовали, какова длина самой короткой -последовательной последовательности как функция от (см., Например, этот поток mathoverflow для краткого изложения). Однако я не смог найти ссылки на сложность их распознавания. Обратите внимание, что, в частности, мы можем легко построить -полные последовательности полинома длины по , а именно, длины , поскольку повторяются раз (любая перестановка может быть реализована с помощью выбирая в -ый блок). Следовательно, мы не можем позволить себе вообще перечислять все перестановки.
Ответы:
Я считаю, что проблема полностью завершена. Я загрузил его как препринт arXiv .
источник