Creatividad polinomial

En la teoría de la complejidad computacional , la creatividad polinomial es una teoría análoga a la teoría de conjuntos creativos en la teoría de la recursividad y la lógica matemática . Los k - conjuntos creativos son una familia de lenguajes formales en la clase de complejidad NP cuyos complementos no tienen, certificadamente, algoritmos de reconocimiento no deterministas en el tiempo.${\displaystyle O(n^{k})}$

Los k conjuntos creativos se conjeturan para formar contraejemplos de la conjetura de Berman-Hartmanis sobre el isomorfismo de conjuntos NP completos . Es NP-complete probar si una cadena de entrada pertenece a cualquiera de estos lenguajes, pero no se conocen isomorfismos de tiempo polinomial entre todos esos lenguajes y otros lenguajes NP-complete. La creatividad polinomial y los conjuntos k- creativos fueron introducidos en 1985 por Deborah Joseph y Paul Young, tras los intentos anteriores de Ko y Moore de definir análogos polinomiales para conjuntos creativos. ^{[1] [2]}

Definición

Joseph y Young definen el conjunto como el conjunto de programas de máquina de Turing no deterministas que, para las entradas que aceptan, tienen una ruta de aceptación con un número de pasos como máximo . Esta notación debe distinguirse con la de la clase de complejidad NP. La clase de complejidad NP es un conjunto de lenguajes formales, mientras que en cambio es un conjunto de programas que aceptan algunos de estos lenguajes. Cada idioma en NP es reconocido por un programa en uno de los conjuntos ; el parámetro es (hasta el factor en el límite del número de pasos) el exponente en el tiempo de ejecución polinomial del programa. ^[1]${\displaystyle \mathrm {NP} ^{(k)}}$${\displaystyle p}$${\displaystyle x}$${\displaystyle |p|(|x|^{k}+1)}$${\displaystyle \mathrm {NP} ^{(k)}}$${\displaystyle \mathrm {NP} ^{(k)}}$${\displaystyle k}$${\displaystyle |p|}$

Según la teoría de Joseph y Young, un lenguaje en NP es k -creativo si es posible encontrar un testigo que demuestre que el complemento de no es reconocido por ningún programa en . Más formalmente, debería existir una función polinomialmente computable que, cuando se le da un programa no determinista en , encuentra una entrada que pertenece y hace que el programa acepte , o que no pertenece y hace que el programa lo rechace . La función se denomina función productiva para . Si esta función productiva existe, el programa dado no produce el comportamiento en la entrada.${\displaystyle L}$${\displaystyle L}$${\displaystyle \mathrm {NP} ^{(k)}}$${\displaystyle f}$${\displaystyle p}$${\displaystyle \mathrm {NP} ^{(k)}}$${\displaystyle x=f(p)}$${\displaystyle L}$${\displaystyle x}$${\displaystyle L}$${\displaystyle x}$${\displaystyle f}$${\displaystyle L}$${\displaystyle x}$que se esperaría de un programa para reconocer el complemento de . ^[1]${\displaystyle L}$

Lo completo

Cada conjunto creativo es NP-completo. Porque, aplicando un argumento de relleno , existe una traducción de tiempo polinomial de las instancias de cualquier otro idioma en NP en programas de tiempo polinomial no deterministas en , de modo que las instancias sí se traducen en programas que aceptan todas las entradas y las instancias no se traducen en programas que rechazan todas las entradas. La composición de esta traducción con la función es una reducción de varios uno en tiempo polinomial del lenguaje dado al conjunto creativo. También es posible demostrar con más fuerza que existe una reducción parsimoniosa invertible al conjunto creativo. ^[1]${\displaystyle k}$${\displaystyle g}$${\displaystyle \mathrm {NP} ^{(k)}}$${\displaystyle f}$ ${\displaystyle k}$${\displaystyle k}$

Existencia

Joseph y Young definen una función de tiempo polinomial para que sea polinomialmente honesta si su tiempo de ejecución es a lo sumo una función polinomial de su longitud de salida. Esto no permite, por ejemplo, funciones que toman tiempo polinomial pero producen salidas de longitud menor que el polinomio. Como muestran, cada función polinomialmente honesta uno a uno es la función productiva de un lenguaje creativo . ^[1]${\displaystyle f}$${\displaystyle f}$${\displaystyle k}$${\displaystyle K_{f}^{k}}$

Dado , Joseph y Young definen como el conjunto de valores para programas no deterministas que tienen una ruta de aceptación para su uso en la mayoría de los pasos. Este número de pasos (en esa entrada) sería consistente con pertenecer a . Luego pertenece a NP, ya que dada una entrada, uno puede adivinar de manera no determinista tanto la ruta de aceptación como su ruta de aceptación, y luego verificar que la ruta es válida para . ^[1]${\displaystyle f}$${\displaystyle K_{f}^{k}}$${\displaystyle f(p)}$${\displaystyle p}$${\displaystyle f(p)}$${\displaystyle |p|(|f(p)|^{k}+1)}$${\displaystyle p}$${\displaystyle \mathrm {NP} ^{(k)}}$${\displaystyle K_{f}^{k}}$${\displaystyle f(p)}$${\displaystyle p}$${\displaystyle p}$

El lenguaje es creativo, con su función productiva, porque cada programa en es mapeado por un valor que es aceptado por (y por lo tanto también pertenece a ) o rechazado por (y por lo tanto tampoco pertenece a ). ^[1]${\displaystyle K_{f}^{k}}$${\displaystyle k}$${\displaystyle f}$${\displaystyle p}$${\displaystyle \mathrm {NP} ^{(k)}}$${\displaystyle f}$${\displaystyle f(p)}$${\displaystyle p}$${\displaystyle K_{f}^{k}}$${\displaystyle p}$${\displaystyle K_{f}^{k}}$

Aplicación a la conjetura de Berman-Hartmanis

La conjetura de Berman-Hartmanis establece que existe un isomorfismo de tiempo polinomial entre dos conjuntos NP-completos cualesquiera: una función que mapea las instancias sí de uno de esos conjuntos uno a uno en instancias sí del otro, toma tiempo polinomial, y cuya función inversa también se puede calcular en tiempo polinomial. Fue formulado por Leonard C. Berman y Juris Hartmanis en 1977, basándose en la observación de que todos los conjuntos NP completos conocidos en ese momento eran isomorfos. Una formulación equivalente de la conjetura es que todos los juegos NP-completos son acolchados . Esto significa que existe una transformación de uno a uno polinomial-temporal y polinomial-tiempo-invertible de instancias sí a instancias sí más grandes que codifican la información "irrelevante" . ^[3]${\displaystyle h(x,y)}$${\displaystyle x}$${\displaystyle y}$

Sin embargo, se desconoce cómo encontrar tal transformación de relleno para un lenguaje creativo cuya función productiva no es polinomial-tiempo-invertible. Por lo tanto, si existen permutaciones unidireccionales , los lenguajes creativos que tienen estas permutaciones como funciones productivas proporcionan contraejemplos candidatos a la conjetura de Berman-Hartmanis. ^[1]${\displaystyle k}$${\displaystyle k}$

La conjetura (no probada) de Joseph-Young formaliza este razonamiento. La conjetura establece que existe una función de aumento de longitud unidireccional tal que no se puede rellenar. ^[1] Alan Selman observó que esto implicaría una conjetura más simple, la conjetura del conjunto completo cifrado : existe una función unidireccional tal que (el conjunto de instancias sí para el problema de satisfacibilidad ) y no son isomórficas. ^[4] Existe un oráculo relativo al cual existen funciones unidireccionales, ambas conjeturas son falsas y la conjetura de Berman-Hartmanis es verdadera. ^[5]${\displaystyle f}$${\displaystyle K_{f}^{k}}$ ${\displaystyle f}$${\displaystyle \mathrm {SAT} }$${\displaystyle f(\mathrm {SAT} )}$

Referencias

1. José, Débora ; Young, Paul (1985), "Algunas observaciones sobre las funciones de testigos para conjuntos no polinomiales y no completos en NP" , Theoretical Computer Science , 39 (2-3): 225-237, doi : 10.1016 / 0304-3975 (85) 90140-9 , MR  0821203
2. Ko, Ker-I; Moore, Daniel (1981), "Completitud, aproximación y densidad", SIAM Journal on Computing , 10 (4): 787–796, doi : 10.1137 / 0210061 , MR 0635436 
3. Berman, L .; Hartmanis, J. (1977), "Sobre isomorfismos y densidad de NP y otros conjuntos completos" (PDF) , SIAM Journal on Computing , 6 (2): 305–322, doi : 10.1137 / 0206023 , hdl : 1813/7101 , Señor 0455536  
4. Selman, Alan L. (1992), "Un estudio de funciones unidireccionales en la teoría de la complejidad", Teoría de sistemas matemáticos , 25 (3): 203-221, doi : 10.1007 / BF01374525 , MR 1151339 , S2CID 33642595  
5. Rogers, John (1997), "La conjetura del isomorfismo se cumple y las funciones unidireccionales existen en relación con un oráculo", Journal of Computer and System Sciences , 54 (3): 412–423, doi : 10.1006 / jcss.1997.1486 , MR 1463764