Podría parecer que no es para tanto, cuando sí. Es posible dirigirse a un matemático para hacerle una pregunta técnica y, acto seguido, éste te puede responder tanto sí como no y ambas respuestas serían exactas.
No es fácil de explicar, cuando sí de entender al concebir la historia de las matemáticas y tener capacidad para analizar sus demostraciones. Algo que muchas personas jamás admitirían es tener que aceptar que trabajar bajo los parámetros de la exactitud puede ser independiente de obtener una propiedad del tercero excluído (excluded middle). Es decir: dos personas en oposición pueden ofrecernos afirmaciones exactas.
Sin embargo, siempre se puede considerar la existencia de un cierto grado de difusión en la lógica usada, un trabajo de posibilidades. Esto es debido a que, por un lado, trabajaríamos con dos filosofías pero, por el otro, también podemos asegurar que una filosofía tiene más rigor que otra. En cualquier caso, la exactitud es una propiedad que no funciona con el mundo real, y es por ello que a la hora de jugar con palabras como relevancia (sound) y coherencia podremos comprender un poco mejor cómo encajar todas las piezas.
Es decir, cuanto más idealizado es un modelo y más preciso en sus cálculos más difícilmente podremos ver que se hace relevante en el mundo real. Esto es lo que pasa con la filosofía más constructivista, que nos ofrece una matemática perfecta para la ingeniería y, al mismo tiempo, no aprovecha todo el potencial de la maquina y lo que puede representarse en ella - lo que puede percibir.
Por otro lado, cuando más relevante sea el planteamiento con el que trabajar es probable que adquiera cierta clase de imprecisiones que emergerán a la hora de aplicar principios de transitividad, escalabilidad, o de llevar los resultados al límite. Entonces los resultados seguirán siendo exactos, pero la relevancia puede perder precisión dentro de su propia coherencia. Y esto es lo que pasa con la filosofía más formal, su manera de programar no es necesariamente extrapolable a otras máquinas.
En informática se ha hablado de dos filosofías fácilmente reconocibles por la literatura: los conectivistas y los conexionistas. Entendiendo que el conexionista rescataría la historia de las matemáticas de los formalistas y axiomáticos, mientras que los conectivistas se centrarían más en los resultados más constructivistas.
La antigua Grecia defendía principios constructivistas, todo viene del 1, y las matemáticas descubrió una enorme amalgama de teoremas gracias a los cambios de filosofía de demostración al incorporar reducciones al absurdo, así como la creación de un lenguaje lógico que dé soporte a las definiciones matemáticas. Lo que se defiende en este blog es que el formalismo o la definición de las matemáticas mediante lenguajes lógicos pueden hacer sus aplicaciones más relevantes, pero al mismo tiempo perderán precisión de una manera tan sutil que no afectará a su exactitud: su capacidad para aseverar cualquier afirmación al 100% en comparación con cualquier apreciación científica que provenga de la medición.
Ahora bien, aún habiendo dos filosofías todavía podremos volver a dividirlas en dos secciones adicionales para descubrir hasta cuatro filosofías que trascienden a cualquier forma de pensamiento mundana: el constructivismo puede ser puro o mixto dependiendo de si se acepta la creación de máquinas mediante afirmaciones demostradas por refutación y, de la misma manera, tenemos dos tipos de demostraciones formales: unas que se basan en la holgura de las inecuaciones y otras que están ausentes de toda holgura.
Para entender esa división mucho más sutil cogeremos dos demostraciones matemáticas: la que uso para deducir que #SAT está dentro de la clase FP y la demostración que dice que SAT está dentro de la clase NP-co.
Cuando leemos con atención la demostración de Cook que asevera que si se resuelve SAT en tiempo polinomial entonces para cada problema dentro de NP existirá una resolución polinonial, en mis ensayos suelo hacer incapié en la variable FORMAL del que se vale para construir la demostración. En la medida de que no conozcamos el valor de la variable y la usemos para construir una configuración de máquina de Turing estaremos dando una demostración formal, no constructiva.
El teorema de Cook decía lo siguiente: cualquier lenguaje L, de estar en NP el problema de la pertenencia a L, podremos asegurar que debe existir una configuración dentro de una máquina de Turing donde dado un oráculo de valores y tras un tiempo acotado polinomialmente podríamos validar que tales valores cumplen la pertenencia. Es decir, el oráculo, limitado dentro de un espacio de trabajo polinomial, será capaz de validar una entrada dentro de L en tiempo polinomial. Determinar cómo fue el oráculo capaz de adivinar la configuración de tales engranajes sería otro problema.
Así que dice Cook: determinar la pertenencia de la entrada a L supone un coste polinomial dentro de un punto de vista no determinístico. Lo cual es exacto. Y le da valor a esa cantidad de tiempo.
N < P(|x|)
N será el tiempo que necesita la máquina para deducir si x pertenece a L partiendo de un enfoque no determinista, donde |x| es el tamaño de la entrada y P(·) es una expresión polinomial.
La demostración de Cook continúa diciendo cómo se configuraría la máquina de Turing usando el valor N como si lo conociéramos. Y, gracias a eso, se determina que existe al menos un problema dentro de la clase NP-completo, que se usará como referencia para seguir introduciendo más problemas dentro de la clase.
Cuando observamos mi demostración de que #SAT está en FP el enunciado es simple: la misma clase que dice Cook que es NP-Co (SAT) yo la endurezco calculando el número de casos que satisfacen tal fórmula (#SAT) y considero que forma parte de la clase FP (la clase de funciones que devuelve un entero en tiempo polinomial).
Al combinar ambos resultados se obtiene como conclusión inapelable de que NP = P.
La demostración se vale de la existencia de una variable V. La variable asegura que el número de variables que se usan en la fórmula será menor que V. Debido a que no puedo saber cuántas variables se usan en la fórmula la demostración, que construye un manual que resuelve un problema en #P, se genera desde un punto de vista formal.
Huelga mencionar que el código que demuestra que SAT está en P es una demostración constructivista y que, por tanto, le puede valer perfectamente a los esquemas formalistas, porque, como ya mencioné, la precisión del constructivismo es mayor que la del formalismo matemático.
Ahora bien, la variable V nos permite crear un libro real, con sus páginas y sus líneas, tal como describo en la demostración. Lo que nos dice que, formalmente, siempre existirá una máquina de Turing que sea capaz de resolver en tiempo polinomial el cálculo citado. Sólo partimos de un conocimiento que sabemos que es exacto:
V < infinito
Ahora bien, tenemos dos demostraciones formales y, al mismo tiempo, son diferentes. Una demostración recoge una variable dentro de un lenguaje hipotético y la otra infiere la variable de la entrada y, aunque la variable escogida por Cook parece más precisa en realidad es exactamente al revés: para cada entrada siempre podremos asegurar que el número de variables será menor que un valor, por lo que siempre existirá una cantidad abierta (infinita) de máquinas de Turing que resuelvan el problema para esa entrada. Sin embargo, la variable escogida por Cook sólo resolverá el problema para una cantidad cerrada (un único caso, y los que se le parezcan mucho) de máquinas de Turing.
Ese formalismo cerrado se puede deducir rápidamente mediante una cuestión:
Si yo tuviera un algoritmo que resolviera SAT en tiempo polinomial, ¿podría valerme del teorema de Cook para convertir cualquier lenguaje dentro de NP a resolución polinomial?
La respuesta es no: porque es una demostración formal CERRADA, sin holgura.
La entrada del teorema de Cook era cualquier lenguaje, sin embargo la entrada de mi teorema es cualquier fórmula booleana.
Si dispongo de una fórmula que no sobrepase un cierto número de variables, ¿podría valerme la construcción que genera mi demostración?
La respuesta es sí: porque es una demostración formal ABIERTA, con holgura V para las variables.
Esos son los matices que quería introducir para intentar hablar con un poco más de propiedad: ya que no se pueden combinar tan fácilmente algunos teoremas matemáticos, por muy exactos que sean.
No hay comentarios:
Publicar un comentario