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.
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.
7 Comments:
¡Dios!, DrZito, que yo estudié letras, y ya no solo es eso, si no que siempre me quedaron las matemáticas para Septiembre.
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.
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. :)
Lo que le pasa a usted, amorosa mía, es que no puede compararse con mi poder... BWA HA HA HA!
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!!
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.
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
<< Home