Here is a decision problem analog of the Towers of Hanoi problem: given a string

Question

Here is a decision problem analog of the Towers of Hanoi problem: given a string that represents a series of Towers of Hanoi moves, decide whether the moves in that string legally move a tower of n disks from pole 1 to pole 3, given that poles 2 and 3 are initially empty. Assume that the input is encoded as the value of n, as a base 10 integer, followed by the moves. Letting the poles be numbered 1, 2, and 3, a move can be encoded as a pair of numbers from {1,2,3} with the first number representing the pole to take a disk from, and the second the pole to place it on.

Determine whether this problem is in P, NP, or co-NP, and give an argument to support your answer. (Hint: if you find your answer unintuitive, think about how long the input is.)

Explanation / Answer

Towers of Hanoi problem is quite easy to understand the problem and find its solution. Also, it is easy to write a program to solve the problem. But, the difficulty is it takes extremely long time to run for any "reasonably" large value of n. It takes exponential running time ie, ?(2n). Here complete verification of the solution requires examining each move which makes verification at least as hard as the solution. So Tower of Hanoi is not in NP or in P (so far). It is NP-hard.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.