Я столкнулся со следующими сомнениями в сложности Ханойских башен , на которые мне хотелось бы получить ваши комментарии.
Это в НП? Попытка ответа: предположим, что Пегги (проверяющий) решает проблему и передает ее Виктору (проверяющему). Виктор может легко увидеть, что окончательное состояние решения правильное (в линейном времени), но у него не останется иного выбора, кроме как пройти каждый ход Пегги, чтобы убедиться, что она не сделала незаконный ход. Так как Пегги должна сделать минимум 2 ^ | диска | - 1 ход (доказуемо), Виктор тоже должен последовать их примеру. Таким образом, у Виктора нет проверки полиномиального времени (определение NP), и, следовательно, он не может быть в NP.
Это в PSPACE ? Вроде бы так, но я не могу придумать, как расширить вышеприведенные рассуждения.
Это PSPACE-полный? Кажется нет, но у меня есть только смутная идея. Автоматизированное планирование, конкретным экземпляром которого является ToH, является PSPACE-полным. Я думаю, что планирование имеет гораздо более сложные случаи, чем ToH
Обновлено : Input = , количество дисков; Выход = конфигурация диска на каждом шаге. После обновления я понял, что этот формат ввода / вывода не подходит для решения проблемы. Я не уверен в правильной формализации, чтобы захватить понятия NP, PSPACE и т. Д. Для такого рода проблемы.
Обновление № 2 : После комментариев Каве и Джеффа я вынужден уточнить проблему:
Пусть на входе будет пара целых где - количество дисков. Если последовательность шагов, предпринятых дисками, записана в формате (номер диска, from-peg, to-peg) (номер диска, from-peg, to-peg) ... от первого хода к последний и закодированный в двоичном виде, выведите i- й бит.
Дайте мне знать, если мне нужно быть более конкретным в отношении кодировки. Я полагаю, комментарий Каве применим в этом случае?
Ответы:
Нет, проблема, которую вы описали, на самом деле довольно проста. Причина высокого уровня заключается в том, что индекс имеет длину примерно n бит, поэтому мы можем позволить себе тратить время на полиномиальное значение от n .я N N
Рассмотрим следующую связанную задачу: Для двух целых чисел и k опишите k- й ход в решении головоломки с n- диском. Размер ввода lg n + lg k < n + lg k , но на самом деле имеет значение только младший значащий бит из n . Таким образом, даже если lg k значительно меньше n , мы можем решить эту проблему во временном полиноме от O ( log k ) .N К К N Л.Г.n + lgk < n + lgК N Л.Г.К N O ( журналк )
Предположим, диски пронумерованы от до нуля в порядке возрастания по размеру, а колышки пронумерованы 0 = источник, 1 = место назначения и 2 = запасной. Запишем k = ( 2 p + 1 ) ⋅ 2 d для некоторых целых чисел p и d . Затем на очереди k :0 k = ( 2 p + 1 ) ⋅ 2d п d К
Мы можем легко вычислить и d во времени O ( log k ) , просматривая двоичное представление k от младшего значащего бита вверх. Вот и все.п d O ( журналк ) К
Теперь предположим, что вам действительно нужен й бит в выходной последовательности, где i является частью ввода вместо k . Если каждый ход кодируется с использованием одного и того же числа битов, в частности, lg ( n + 1 ) битов для номера диска, 2 битов для исходной peg и 2 битов для промежуточной peg - тогда нам просто нужно вычислить k- й ход, где k = ⌊ i / ( lg ( n + 1 ) + 4 ) ⌋я я К Л.Г.( n + 1 ) 2 2 К k = ⌊ i / ( lg( n + 1 ) + 4 ) ⌋ , а затем извлечь соответствующий бит. (Обратите внимание, что является линейным по входному размеру, так как нам нужно знать n, чтобы определить выход.)Л.Г.( n + 1 ) + 4 N
С другой стороны, если мы используем представление переменной длины для номеров дисков, то мы можем найти число за полиномиальное время с помощью бинарного поиска. Нам нужно знать общее количество оборотов, необходимое для перемещения верхних m дисков, для всех m ≤ k , но это определяется повторением M ( m ) = 2 M ( m - 1 ) + ( \ #bits для записи перемещения диск m ), который мы можем оценить за полиномиальное время с помощью динамического программирования. Остальные детали оставлены читателю как скучное упражнение.К м м ≤ к
(Я предполагаю, что я сделал по крайней мере одну ошибку по одному или четность, но, надеюсь, основная идея ясна.)
источник