Complexidade das torres de Hanói

Encontrei as seguintes dúvidas sobre a complexidade das Torres de Hanói , sobre as quais gostaria de seus comentários.

Está em NP? Resposta da tentativa: Suponha que Peggy (provador) resolva o problema e o envie a Victor (verificador). Victor pode ver facilmente que o estado final da solução está correto (em tempo linear), mas ele não terá outra opção a não ser passar por cada um dos movimentos de Peggy para garantir que ela não faça um movimento ilegal. Como Peggy precisa fazer no mínimo 2 ^ | discos | - 1 jogada (provável), Victor também tem que seguir o exemplo. Assim, Victor não tem verificação de tempo polinomial (a definição de NP) e, portanto, não pode estar em NP.
Está no PSPACE ? Parece que sim, mas não consigo pensar em como estender o raciocínio acima.
É PSPACE completo? Parece que não, mas tenho apenas uma vaga idéia. O Planejamento automatizado, do qual ToH é uma instância específica, é completo no PSPACE. Eu acho que o Planejamento tem instâncias muito mais difíceis que o ToH.

Atualizado : Input = $n$ , o número de discos; Saída = configuração do disco em cada etapa. Depois de atualizar isso, percebi que esse formato de entrada / saída não se encaixa em um problema de decisão. Não tenho certeza da formalização correta para capturar as noções de NP, PSPACE etc. para esse tipo de problema.

Atualização # 2 : Após os comentários de Kaveh e Jeff, sou forçado a tornar o problema mais preciso:

Seja a entrada o par de entradas $(n,i)$ que $n$ é o número de discos. Se a sequência de movimentos executados pelos discos for anotada no formato (número do disco, de peg, para peg) (número de disco, de peg, para peg) ... desde o primeiro movimento até o por último, e codificado em binário, gera o $i$ bit.

Deixe-me saber se preciso ser mais específico sobre a codificação. Suponho que o comentário de Kaveh se aplique neste caso?

complexity-theory time-complexity PKG
fonte

você poderia por favor definir o problema das Torres de Hanói ou vincular-se a uma definição?

Kaveh

PKG, eu sei o que é a Torre de Hanói. Eu quis dizer qual é o problema computacional que você deseja conhecer sua complexidade? Qual é a entrada? Qual é a saída?

Kaveh

@Kaveh: Sua intenção era clara do seu primeiro comentário

PKG

Desculpe. Aliás, existem classes de complexidade de funções, elas geralmente têm um F antes ou depois do nome, verifique o zoológico de complexidade para obter definições.

Kaveh

Assim é o inteiro

também parte da entrada?

i

$i$

jeffe

Respostas:

Não, o problema que você descreveu é realmente bastante fácil. A razão de alto nível é que o índice tem aproximadamente bits de comprimento, para que possamos gastar tempo polinomial em . $i$ $n$ $n$

Considere o seguinte problema relacionado: Dados dois números e , descreva o ésimo movimento na solução do quebra-cabeça disco. O tamanho da entrada é , mas, na verdade, apenas o bit menos significativo de importa. Portanto, mesmo que seja significativamente menor que , podemos resolver esse problema no polinômio do tempo em . $n$ $k$ $k$ $n$ $\lg n + \lg k < n + \lg k$ $n$ $\lg k$ $n$ $O(\log k)$

Suponha que os discos sejam numerados de a qualquer que seja em ordem crescente de tamanho, e os pinos são numerados 0 = origem, 1 = destino e 2 = sobressalentes. Escreva para alguns números inteiros e . Em seguida, no turn : $0$ $k = (2p+1)\cdot 2^d$ $p$ $d$ $k$

Se é ímpar, o disco passa do pino para o pino . $d+n$ $d$ $(p\bmod 3)$ $((p+1)\bmod 3)$
Se for par, o disco move o pino do formulário para o pino . $d+n$ $d$ $(-p\bmod 3)$ $((-p-1)\bmod 3)$

Podemos calcular facilmente e no tempo fazendo um loop pela representação binária de do bit menos significativo para cima. É isso aí. $p$ $d$ $O(\log k)$ $k$

Agora, suponha que você realmente queira o bit na sequência de saída, em que faz parte da entrada em vez de . Se cada turno for codificado usando o mesmo número de bits - especificamente, bits para o número do disco, bits para o from-peg e bits para o to-peg -, basta calcular o movimento, onde $i$ $i$ $k$ $\lg(n+1)$ $2$ $2$ $k$ $k = \lfloor{i/(\lg(n+1)+4)\rfloor}$ e extraia o bit apropriado. (Observe que é linear no tamanho da entrada, pois precisamos saber para determinar a saída.) $\lg(n+1)+4$ $n$

Por outro lado, se estivermos usando uma representação de tamanho variável para os números de disco, podemos encontrar o número de movimentação em tempo polinomial por pesquisa binária. Precisamos saber o número total de voltas necessárias para mover os discos superiores , para todos os , mas isso é dado pela recorrência que podemos avaliar em tempo polinomial por programação dinâmica. Os detalhes restantes são deixados como um exercício chato para o leitor. $k$ $m$ $m\le k$

M (m) = 2 M (m - 1) + (\ #bits para gravar o disco em movimento m)

$M(m) = 2M(m-1) + (\text{\#bits to record moving disk } m)$

(Suponho que cometi pelo menos um erro de paridade ou de um por um, mas espero que a ideia principal seja clara.)

JeffE
fonte