He caído en una pista posiblemente falsa

Vaya..., parece que no siempre lo tendré tan fácil. Ha sido empezar a documentarme y descubrir que, al final de todo, todo confluye en dos documentos - documentos que exigen alguna clase de pago.




Es curioso cómo, a la hora de la verdad, la ingeniería tiene puntos oscuros que no puede justificar. Por muy globalizada que esté la red, hay teoremas que son demasiado fundamentales como para no ser compartidos. Y, claro, el asunto es que huele..., huele un poquito mal.

Con el fin de completar mi línea de Bingo, considerando que no paro de escribir sobre complejidad algorítmica y cosas así, pensé lógico embarcarme en el tema de P-completo, ya que tengo una buena base para rematarlo.

Pero claro, no quería limitarme a decir lo que sé, quería mostrar un código de ejemplo, distintas maneras de afrontar el asunto en cuestión... Y claro, al final observo que, al final del túnel tenemos a un viejo conocido: Stephen Cook.

Aún así le quise dar una oportunidad, ¿es posible que nos la haya jugado con una demostración formalista y que no podamos asociarlo con poder crear código OTRA VEZ? Eso explicaría que el tema de P-Co sea algo que sólo lo he visto desarrollado en la informática teórica. De hecho, afecta esas conclusiones demasiado a la manera de crear código.

Recuerdo en la universidad que, en una ocasión, unos compañeros se obsesionaron conque era imposible resolver un código de una cierta manera, porque no veían la manera. Tenía que ver con introducir algo de contexto a una expresión regular. Ellos creían que sólo se podía resolver mediante una pila, yo les demostré que se podía crear un registro con un número limitado de variables, tantas como anidamientos tenía el bucle. Entre las motivaciones que me daban de que no se podía hacer alguno mencionaba esta limitación teórica: la que establecía la tesis de P-Co si coincide o no con NC.

La verdad es que el tema me pareció interesante, y me puse a desarrollarlo. Pero claro, nada más leer que algo equivale a algo busco la demostración, o me la hago. Aquí empieza el asunto. Ya he desarrollado bastante código y todo apunta mal..., muy mal. La aplicabilidad de todo esto apunta a que es meramente teórico - no parece que afecte al código. Las equivalencias obligan a resolver las expresiones como si...

El principal problema está en la afirmación de Cook al decir que el reconocimiento de una palabra en una gramática libre de contexto se traduce en un digrafo acíclico - para que eso sea así habría que repetir los símbolos no terminales para que se parezcan a su problema del Path Systems. Eso quiere decir que tendría que trabajar con el tamaño de la entrada para constituir la estructura del problema. Pues bien, con la estructura es con lo que se hacen las llamadas a otros procesadores en paralelo, si la estructura depende de la entrada entonces no tenemos una red para cualquier entrada, lo tenemos para entradas específicas - ¡ha ocurrido lo mismo que con NP Vs P!

Si al defender lo que he defendido me he vuelto antipopular..., ¡ya me imagino con estos otros asuntos! Además, esas demostraciones se han vuelto inaccesibles. Y yo me digo, siendo tan antiguas y unos pilares tan importantes para asegurarnos de que realmente lo que se estudia asegura cosas reales, y no unicornios voladores, ¡qué mínimo que mostrar tales demostraciones en vez de asegurar su existencia!

Así que, ¿qué hago? ¿Le pongo una señal apestosa para no tocar el tema? ¿Qué hago si alguien me pregunta sobre P-Completo? La teoría es fácil, y tiene puntos fascinantes - pero claro, ¿afecta a la ingeniería como se asegura o sólo en parte? ¿Y en qué sentido? Hay conexiones que he estado buscando y no ha habido manera.

El principal problema es que, como pasaba la otra vez, si realmente se me asegura que el grafo es acíclico entonces puedo asegurar que P-Co=NC y la hemos líado de nuevo, porque me valdría de ese código para implementar un sistema de multiprocesadores en paralelo - ahora bien, no veo la conexión a la hora de construir el código. Es como si dijéramos que, formalmente, existiría una manera de hacerlo..., lo cual es algo con lo que especialmente no estaría muy de acuerdo, pues las demostraciones constructivas imponen una exigencia adicional.

Nada, pues habrá que dejarlo en cuarentena - ya tocaré otro tema.