\n<\/p>\n
Heule, sin embargo, encontr\u00f3 estimulante el descubrimiento de resultados pasados. Demostr\u00f3 que otros investigadores encontraron el problema lo suficientemente importante como para trabajar en \u00e9l, y le confirm\u00f3 que el \u00fanico resultado que val\u00eda la pena obtener era resolver el problema por completo.<\/p>\n
\u201cUna vez que nos dimos cuenta de que hab\u00eda habido 20 a\u00f1os de trabajo en el problema, eso cambi\u00f3 completamente la imagen\u201d, dijo.<\/p>\n
Evitando lo vulgar<\/p>\n
A lo largo de los a\u00f1os, Heule hab\u00eda hecho carrera encontrando formas eficientes de buscar entre vastas combinaciones posibles. Su enfoque se llama resoluci\u00f3n SAT, abreviatura de \u00absatisfacibilidad\u00bb. Implica construir una f\u00f3rmula larga, llamada f\u00f3rmula booleana, que puede tener dos resultados posibles: 0 o 1. Si el resultado es 1, la f\u00f3rmula es verdadera y el problema est\u00e1 satisfecho.<\/p>\n
Para el problema de coloraci\u00f3n del empaquetamiento, cada variable en la f\u00f3rmula podr\u00eda representar si una celda determinada est\u00e1 ocupada por un n\u00famero determinado. Una computadora busca formas de asignar variables para satisfacer la f\u00f3rmula. Si la computadora puede hacerlo, sabr\u00e1 que es posible empaquetar la cuadr\u00edcula en las condiciones que ha establecido.<\/p>\n
Desafortunadamente, una codificaci\u00f3n sencilla del problema del color del empaque como una f\u00f3rmula booleana podr\u00eda extenderse a muchos millones de t\u00e9rminos: una computadora, o incluso una flota de computadoras, podr\u00eda funcionar para siempre probando todas las diferentes formas de asignar variables dentro de ella.<\/p>\n
\u201cTratar de hacer esta fuerza bruta tomar\u00eda hasta que el universo termine si lo hicieras ingenuamente\u201d, dijo Goddard. \u00abAs\u00ed que necesitas algunas simplificaciones geniales para reducirlo a algo que sea incluso posible\u00bb.<\/p>\n
Adem\u00e1s, cada vez que agregas un n\u00famero al problema de coloraci\u00f3n del empaque, se vuelve unas 100 veces m\u00e1s dif\u00edcil, debido a la forma en que se multiplican las posibles combinaciones. Esto significa que si un banco de computadoras trabajando en paralelo pudiera descartar 12 en un solo d\u00eda de c\u00f3mputo, necesitar\u00edan 100 d\u00edas de tiempo de c\u00f3mputo para descartar 13.<\/p>\n
Heule y Subercaseaux consideraban que escalar un enfoque computacional de fuerza bruta era vulgar, en cierto modo. \u201cTen\u00edamos varias ideas prometedoras, por lo que adoptamos la mentalidad de ‘Intentemos optimizar nuestro enfoque hasta que podamos resolver este problema en menos de 48 horas de computaci\u00f3n en el cl\u00faster’\u201d, dijo Subercaseaux.<\/p>\n
Para hacer eso, tuvieron que idear formas de limitar la cantidad de combinaciones que el cl\u00faster de computaci\u00f3n ten\u00eda que probar.<\/p>\n
\u201c[They] no solo quiero resolverlo, sino resolverlo de una manera impresionante\u201d, dijo Alexander Soifer de la Universidad de Colorado, Colorado Springs.<\/p>\n
Heule y Subercaseaux reconocieron que muchas combinaciones son esencialmente iguales. Si est\u00e1 tratando de llenar un mosaico en forma de diamante con ocho n\u00fameros diferentes, no importa si el primer n\u00famero que coloca es uno arriba y uno a la derecha del cuadrado central, o uno abajo y uno a la izquierda de la plaza del centro. Las dos ubicaciones son sim\u00e9tricas entre s\u00ed y restringen su pr\u00f3ximo movimiento exactamente de la misma manera, por lo que no hay raz\u00f3n para verificarlas a ambas.<\/p>\n