Guerra De Clases

Era una oscura noche en las calles del dominio de los problemas decidibles. A lo lejos podía escucharse el clamor de la eterna batalla entre dos clanes hermanos. La milenaria guerra de sus ancestros. La incesante búsqueda de la igualdad. Mas el problema del clasismo se había vuelto más fuerte en las últimas décadas. Si bien algunos pocos oprimidos defendían la igualdad entre clases, gran parte del mundo estaba convencida de que no existía siquiera comparación posible. Los clanes de P y NP continuarían luchando hasta el fin de los tiempos.

La guerra se hacía cada vez más intensa. Pequeñas familias se unían y el poder entre ellos se complementaba. Turbios negocios se realizaban en la intersecciones de las oscuras calles. El presente era cada vez más gris, y el futuro no parecía aclarar las nubes.

Un pequeño grupo de NP's extremistas, llamados los NP-completos, se aliaron con el clan de lambda y construyeron temibles robots que acabarían con las filas del clan P. Malvados y sin compasión los soltaron a las calles. No pasó mucho tiempo antes de que todos comenzaran a temer a estas máquinas asesinas, terribles autómatas conocidos como las Maquinas de Turing. Sin mucho esfuerzo lograron acabar con el clan P, tomando solo algunos como prisioneros en su prisión de alta seguridad, la implacable prisión del Contexto.

Todas las noches los miembros del clan P veían la estrellas. La más brillante de ellas era la estrella de Kleene. El mundo había sido dominado por el clan NP y las temibles máquinas de Turing aún seguían causando desastres. No se podía continuar así. Un grupo de P's organizó un plan para escapar de la prisión, rescatar al mundo y terminar con la guerra. Con piezas que encontraron a través del patio y las celdas, y una batería recargable que había logrado conservar uno de ellos, construyeron un autómata de pila que distraería a los guardias mientras ellos escapaban.

Pusieron su plan en marcha. Mientras el autómata intentaba reconocer a los guardias y ellos al autómata, un pequeño grupo de P's, camuflajeados en ceros y unos, treparon el muro de la prisión del Contexto hacia la libertad. Una vez afuera, se convirtieron en la única esperanza, incansables luchadores por la paz. A partir de ese momento, fueron conocidos como los legendarios Lenguajes Libres de Contexto.

Para su sorpresa, no pudieron encontrar tampoco rastro del clan NP. Al parecer, las Máquinas de Turing se habían rebelado y habían logrado dominar el espacio. Su malvado líder, la máquina ATM había llevado el mundo a la miseria.

Tendrían que considerar un nuevo plan. Contaba la leyenda que existía un viejo y sabio miembro del clan NP que podría ayudarlos. Sin otra opción, se encaminaron a encontrarlo. Después de un arduo y largo viaje, se encontraron frente a frente a las puertas de un imponente templo. Las puertas estaban cerradas con un gigantesco tronco que mostraba tres iniciales: S. A. T. No terminaron de pronunciar las iniciales cuando se abrieron las puertas y salió un pobre anciano.

Los Lenguajes Libres de Contexto pidieron su consejo al anciano. Consejos sobre como derrotar a la temible máquina ATM y sus seguidores. El anciano levantó la vista y dijo: "La debilidad de ATM está en su poder de decisión". De inmediato, una luz brillante comenzó a emanar del anciano y en un instante, éste desapareció en el aire. Extrañados, los Lenguajes preguntaron a los demás habitantes del templo, que había ocurrido. Pero todos respondieron lo mismo: "Estamos felices por SAT. Pues al fin ha encontrado la verdad".

Así, se fueron valientes a enfrentar a las temibles Maquinas de Turing. Llegaron rápidamente al centro de mando. A un lado, estaba una puerta que decía "NP". Era evidente que allí tenían prisioneros a sus antiguos rivales. Se decidieron a rescatarlos, pero no pudieron avanzar más de un paso cuando se vieron prisioneros de mil cintas que parecían provenir de todos lados. Los Lenguajes lucharon sin éxito, hasta que desde la oscuridad se hizo ver el feroz líder de las máquinas, el poderoso ATM. Implacable, llenó de miedo a los Lenguajes Libres de Contexto.

Uno de estos Lenguajes, por ser finito, logró escapar de las cintas sin ser detectado. Mientras ATM se deleitaba en su victoria, el Lenguaje empujó a una de las máquinas que acompañaba al líder e hizo que cayera sobre el mismo. Por más que ATM intentaba reconocer lo que estaba pasando, no parecía poder decidirse. Aprovechando la confusión, los Lenguajes Libres de Contexto escaparon sus riendas y liberaron al clan NP. Juntos, obligaron al resto de la máquinas de Turing a unirse a la indecisa máquina ATM, quedando presos en sus cintas por el resto de la eternidad.

Así los clanes P y NP hicieron las paces. La guerra acabó y las máquinas fueron detenidas. Liberaron a sus compañeros aún encarcelados. Y sin saber aún si provenían de un mismo linaje o no, pudieron coexistir en paz, en el amplio espacio de los problemas decidibles.