martes, mayo 31, 2005

El Buscaminas es NP-completo

Un problema es P-completo cuando existe un algoritmo que lo resuelve en tiempo polinomial, es decir en un máximo número de pasos expresable como un polinomio en el tamaño del problema. Así sumar dos números de T cifras es un problema P-completo porque se necesitan como mucho 2T-1 pasos para completar la operación.

Que no se conozca un algoritmo para resolver un problema en tiempo polinomial implica que este es “difícil”, pero no que no sea P-completo. Si existe un algoritmo que es capaz de verificar en tiempo polinomial que una propuesta de solución de verdad resuelve el problema, entonces a este se le clasifica como NP-completo.

Resolver un puzzle es un problema NP-completo porque probar todas las posibles combinaciones necesita un número de pasos exponencial en la cantidad de piezas, pero comprobar que está efectivamente hecho solo requiere un golpe de vista.

El Buscaminas es NP-completo. Mejor dicho, el llamado “Problema de la Consistencia del Buscaminas” es NP-completo. Este problema, equivalente a jugar la partida perfecta, consiste en lo siguiente: Márquese uno cuadrito como sospechoso. ¿Existe una distribución de minas que sea consistente con actual configuración de números y la cantidad de minas por descubrir? Pues bien, existe un algoritmo que proporciona una respuesta en tiempo polinomial. Por lo tanto el Buscaminas es NP-completo. (Minesweeper is NP-complete, R. Kaye, Mathematical Intelligencer, 2000).

Tenganlo en cuenta durante su próximo tiempo libre.

8 Comments:

At mayo 31, 2005 4:51 p. m., Anonymous MIniZita said...

¡Dios!, DrZito, que yo estudié letras, y ya no solo es eso, si no que siempre me quedaron las matemáticas para Septiembre.

 
At mayo 31, 2005 6:49 p. m., Blogger Hijo Tonto said...

Es usted un crack, cada día me lo afirma. Yo que no entendia como se jugaba...

Off Topic:

Le he invitado a resolver test o algo así en mi blog. Es musical, no se asuste.

 
At mayo 31, 2005 8:20 p. m., Blogger steviecannell said...

Doctor, le leo desde hace tiempo y debo confesar que le tengo gran aprecio a su blog, por eso he pensado que sería buena idea linkearlo en mi recien nacida bitácora. Pase cuando quiera y coménteme si está conforme.

 
At mayo 31, 2005 10:20 p. m., Anonymous Amanda said...

Minesweeper is Satan! No juego al buscaminas y sobre todo no leo artículos sobre el buscaminas. He tenido que leerme este artículo para darme cuenta de que era sobre el buscaminas y así poder evitar leerlo, menos mal. :)

 
At mayo 31, 2005 10:21 p. m., Anonymous Casimiro aka peón de rey said...

Lo que le pasa a usted, amorosa mía, es que no puede compararse con mi poder... BWA HA HA HA!

 
At mayo 31, 2005 11:22 p. m., Blogger Dr Zito said...

HijoTonto: Guante recogido, gracias. Me ha resuelto usted el post de manyana. Con el dia tan ocupado que tenia!

Mr Cannell: Descuide usted que me pasare, me pasare. Un honor.

Duo del amor: Y dicen que el azucar exacerba la hiperactividad de los ninyos. Menos mal que no les han llegado las galletas!!

 
At junio 13, 2005 10:30 p. m., Anonymous hyDe_ said...

Pues bien, existe un algoritmo que proporciona una respuesta en tiempo polinomial. Por lo tanto el Buscaminas es NP-completo

Esta afirmación es completamente falsa. Si hubiera un algoritmo que proporcionara respuesta en tiempo polinomial, sería un algoritmo Polinómico.

 
At junio 14, 2005 10:43 p. m., Anonymous Bomber said...

y todo esto es para decir que no siempre puedes resolver el buscaminas con logica? vamos, es que no me he enterado de nada, pero es algo obvio...

 

Publicar un comentario en la entrada

<< Home