Сложность Башен Ханоя

20

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

  • Это в НП? Попытка ответа: предположим, что Пегги (проверяющий) решает проблему и передает ее Виктору (проверяющему). Виктор может легко увидеть, что окончательное состояние решения правильное (в линейном времени), но у него не останется иного выбора, кроме как пройти каждый ход Пегги, чтобы убедиться, что она не сделала незаконный ход. Так как Пегги должна сделать минимум 2 ^ | диска | - 1 ход (доказуемо), Виктор тоже должен последовать их примеру. Таким образом, у Виктора нет проверки полиномиального времени (определение NP), и, следовательно, он не может быть в NP.

  • Это в PSPACE ? Вроде бы так, но я не могу придумать, как расширить вышеприведенные рассуждения.

  • Это PSPACE-полный? Кажется нет, но у меня есть только смутная идея. Автоматизированное планирование, конкретным экземпляром которого является ToH, является PSPACE-полным. Я думаю, что планирование имеет гораздо более сложные случаи, чем ToH

Обновлено : Input = , количество дисков; Выход = конфигурация диска на каждом шаге. После обновления я понял, что этот формат ввода / вывода не подходит для решения проблемы. Я не уверен в правильной формализации, чтобы захватить понятия NP, PSPACE и т. Д. Для такого рода проблемы.n

Обновление № 2 : После комментариев Каве и Джеффа я вынужден уточнить проблему:

Пусть на входе будет пара целых(n,i) где - количество дисков. Если последовательность шагов, предпринятых дисками, записана в формате (номер диска, from-peg, to-peg) (номер диска, from-peg, to-peg) ... от первого хода к последний и закодированный в двоичном виде, выведите i- й бит.ni

Дайте мне знать, если мне нужно быть более конкретным в отношении кодировки. Я полагаю, комментарий Каве применим в этом случае?

PKG
источник
5
Не могли бы вы определить проблему Ханойских Башен или ссылку на определение?
Каве
1
PKG, я знаю, что это Ханойская башня. Я имел в виду, в чем вычислительная проблема, которую вы хотите знать, ее сложность? Какой вход? Какой выход?
Каве
@Kaveh: Ваше намерение было неясно из вашего первого комментария
PKG
извиняюсь. Между прочим, существуют классы сложности функций, они обычно имеют F до или после имени, проверьте определения в зоопарке сложности.
Каве
1
Так целое число тоже часть ввода? i
Джефф

Ответы:

9

Нет, проблема, которую вы описали, на самом деле довольно проста. Причина высокого уровня заключается в том, что индекс имеет длину примерно n бит, поэтому мы можем позволить себе тратить время на полиномиальное значение от n .inn

Рассмотрим следующую связанную задачу: Для двух целых чисел и k опишите k- й ход в решении головоломки с n- диском. Размер ввода lg n + lg k < n + lg k , но на самом деле имеет значение только младший значащий бит из n . Таким образом, даже если lg k значительно меньше n , мы можем решить эту проблему во временном полиноме от O ( log k ) .nkknlgn+lgk<n+lgknlgkNО(журналК)

Предположим, диски пронумерованы от до нуля в порядке возрастания по размеру, а колышки пронумерованы 0 = источник, 1 = место назначения и 2 = запасной. Запишем k = ( 2 p + 1 ) 2 d для некоторых целых чисел p и d . Затем на очереди k :0Кзнак равно(2п+1)2dпdК

  • Если нечетно, то диск d перемещается из peg ( p mod 3 ) в peg ( ( p + 1 ) mod 3 ) .d+Nd(пмодификация3)((п+1)модификация3)
  • Если четное, то диск d перемещается из peg ( - p mod 3 ) в peg ( ( - p - 1 ) mod 3 ) .d+Nd(-пмодификация3)((-п-1)модификация3)

Мы можем легко вычислить и d во времени O ( log k ) , просматривая двоичное представление k от младшего значащего бита вверх. Вот и все.пdО(журналК)К

Теперь предположим, что вам действительно нужен й бит в выходной последовательности, где i является частью ввода вместо k . Если каждый ход кодируется с использованием одного и того же числа битов, в частности, lg ( n + 1 ) битов для номера диска, 2 битов для исходной peg и 2 битов для промежуточной peg - тогда нам просто нужно вычислить k- й ход, где k = i / ( lg ( n + 1 ) + 4 ) яяКЛ.Г.(N+1)22ККзнак равноя/(Л.Г.(N+1)+4), а затем извлечь соответствующий бит. (Обратите внимание, что является линейным по входному размеру, так как нам нужно знать n, чтобы определить выход.)Л.Г.(N+1)+4N

С другой стороны, если мы используем представление переменной длины для номеров дисков, то мы можем найти число за полиномиальное время с помощью бинарного поиска. Нам нужно знать общее количество оборотов, необходимое для перемещения верхних m дисков, для всех m k , но это определяется повторением M ( m ) = 2 M ( m - 1 ) + ( \ #bits для записи перемещения диск  m ), который мы можем оценить за полиномиальное время с помощью динамического программирования. Остальные детали оставлены читателю как скучное упражнение.КммК

M(м)знак равно2M(м-1)+(\ #bits для записи движущегося диска м)

(Я предполагаю, что я сделал по крайней мере одну ошибку по одному или четность, но, надеюсь, основная идея ясна.)

JeffE
источник