ApresentaçãoProblemaNP Completo

Instant Insanity GameProblema NP-Completo

Tiago Kautzmann e Sandro Oliveira Dorneles


Quebra-cabeas popularizado no final dos anos 1960 pela companhia Parker Brothers.


O quebra-cabeas consiste de 4 cubos cujas faces so coloridas com vermelho, branco, azul e verde. O objetivo empilhar os cubos de forma que cada um dos quatro lados da pilha exiba todas as quatro cores.


Grafo correspondente verso original do Instant Insanity com as cores (vrtices) verde (G), azul (B), vermelho (R) e branca (W) com os cubos (arestas) representados pelas letras gregas (Beta, psilon, Stigma, Delta).

4 cubos com 4 cores


Soluo para o problema.


Em 1978, Edward Robertson e Ian Munro mostraram que, generalizando o nmero de cores e cubos de 4 para n, o quebra-cabeas Instant Insanity se torna um problema NP-completo.

Foi um dos primeiros estudos de complexidade computacional de quebra-cabeas e jogos.


Para n cubos, existem24n / 8 arranjos possveis. Cada cubo tem 24 posies possveis (6 escolhas de face e 4 rotaes) e 8 o nmero de rotaes possveis da torre.

Cubos (n) Arranjos possveis

4 41472

5 995328

6 23887872

7 573308928

8 13759414272

9 330225942528

10 7925422620672

11 190210142896128

12 4565043429507070


Questo de Deciso (Robertson and Munro, 1978): Dado n cubos, com cada face de cada cubo colorida com uma das n cores, possvel empilhar os cubos de forma que cada cor aparea exatamente uma vez em cada um dos 4 lados da pilha?


No um problema da classe P!!No h algoritmo determinstico que resolva o problema em tempo polinomial. No h algoritmo vivel.No resolveramos o problema do Instant Insanity em um tempo razovel utilizando de fora bruta.

Instant Insanity generalizado


um problema da classe NP!!Uma soluo correta pode ser verificada por um algoritmo no deterministico em tempo polinomial, ou seja, resolvvel no deterministicamente em tempo polinomial.

24n / 8arranjos

possveis



um problema NP-Completo!!!Provado por Robertson e Munro (Artigo NP-Completeness, Puzzles e Games). Reduo em tempo polinomial do problema EXACT COVER (Cobertura Exata) para o problema da verso generalizada do Instant Insanity. Exact Cover um dos 21 problemas NP-Completos de Karp.



um problema NP-Completo!!!Ou seja, foi possvel transformar, em tempo polinomial, um problema Exact Cover em um problema Instant Insanity generalizado. So problemas parecidos.J EXACT COVER um problema NP-Completo, provado atravs da reduo do SAT.


RefernciasEdward Robertson and Ian Munro. NP-completeness, puzzles and games. Utilitas Math, 13:99-116, 1978.

Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Thomas D. Morgan, and Ryuhei Uehara, Variations on Instant Insanity, in Space-Efficient Data Structures, Streams, and Algorithms: Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday (Ianfest-66), Lecture Notes in Computer Science, volume 8066, August 1516, 2013, pages 3347.

COLLISTER, Larry. A computer solution to Instant Insanity. The Two-Year College Mathematics Journal, Vol. 6. No. 2 (May, 1975), pp. 36-41.

KENDALL, Graham, PARKES, Andrew, SPOERER, Kristian. A Survey of NP-Complete Puzzles. ICGA Journal.

TOSCANI, Laira Vieira, VELOSO, Paulo A.S. Complexidade de algoritmos: Anlise, projeto e mtodos. Coleo Livros Didticos UFRGS, volume 13. 3 Edio - Porto Alegre : Bookman, 2012.

Documents

ApresentaçãoProblemaNP Completo