Creatividad polinómica

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 recursión y la lógica matemática . Los conjuntos creativos son una familia de lenguajes formales en la clase de complejidad NP cuyos complementos no tienen algoritmos de reconocimiento no deterministas de tiempo polinomial . Generalmente se cree que NP es diferente de co-NP (la clase de complementos de lenguajes en NP), lo que implicaría con mayor fuerza que los complementos de todos los lenguajes NP-completos no tienen algoritmos de reconocimiento no deterministas de tiempo polinomial. ^{[ 1 ]} Sin embargo, para los conjuntos creativos , se puede demostrar la falta de un algoritmo de reconocimiento (más restringido), mientras que una prueba de que NP ≠ co-NP sigue siendo esquiva.${\displaystyle k}$${\displaystyle O(n^{k})}$${\displaystyle k}$

Se conjetura que los conjuntos creativos constituyen contraejemplos a la conjetura de Berman-Hartmanis sobre el isomorfismo de conjuntos NP-completos. Es NP-completo comprobar si una cadena de entrada pertenece a alguno de estos lenguajes, pero no se conocen isomorfismos de tiempo polinomial entre todos estos lenguajes y otros lenguajes NP-completos. La creatividad polinomial y los conjuntos creativos fueron introducidos en 1985 por Deborah Joseph y Paul Young, tras intentos previos de definir análogos polinomiales para conjuntos creativos por Ko y Moore. ^{[ 2 ] [ 3 ]}${\displaystyle k}$${\displaystyle k}$

Intuitivamente, un conjunto es creativo cuando existe un algoritmo de tiempo polinomial que crea un contraejemplo para cualquier algoritmo de reconocimiento rápido no determinista candidato para su complemento.

Las clases de algoritmos de reconocimiento rápido no deterministas son formalizadas por Joseph y Young como conjuntos de programas de máquinas de Turing no deterministas que, para las entradas que aceptan, tienen una ruta de aceptación con un número de pasos que es como máximo . Esta notación debe distinguirse de la de la clase de complejidad NP. La clase de complejidad NP es un conjunto de lenguajes formales, mientras que es, en cambio, un conjunto de programas que aceptan algunos de estos lenguajes. Cada lenguaje en NP es reconocido por un programa en uno de los conjuntos , con un parámetro que es (salvo el factor en el límite del número de pasos) el exponente en el tiempo de ejecución polinomial del programa. ^{[ 2 ]}${\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 -creativo si es posible encontrar un testigo que demuestre que el complemento de no es reconocido por ningún programa en . Más formalmente, debe existir una función computable polinomialmente que mapee los programas en esta clase a entradas en las que fallan. Cuando se le da un programa no determinista en , la función debe producir una cadena de entrada que o bien pertenece a y hace que el programa acepte , o bien no pertenece a y hace que el programa rechace . La función se llama función productiva para . Si esta función productiva existe, el programa dado no produce el comportamiento en la entrada que se esperaría de un programa para reconocer el complemento de . ^{[ 2 ]}${\displaystyle L}$${\displaystyle k}$${\displaystyle L}$${\displaystyle \mathrm {NP} ^{(k)}}$${\displaystyle f}$${\displaystyle p}$${\displaystyle \mathrm {NP} ^{(k)}}$${\displaystyle f}$${\displaystyle x=f(p)}$${\displaystyle L}$${\displaystyle x}$${\displaystyle L}$${\displaystyle x}$${\displaystyle f}$${\displaystyle L}$${\displaystyle x}$${\displaystyle L}$

Joseph y Young construyen lenguajes creativos invirtiendo las definiciones de estos lenguajes: en lugar de partir de un lenguaje e intentar encontrar una función productiva para él, parten de una función y construyen un lenguaje para el cual esta es la función productiva. Definen una función de tiempo polinomial como polinomialmente honesta si su tiempo de ejecución es como máximo una función polinomial de la longitud de su salida. Esto excluye, por ejemplo, las funciones que toman tiempo polinomial pero producen salidas de menor longitud que la polinomial. Como demuestran, toda función polinomialmente honesta biyectiva es la función productiva para un lenguaje -creativo . ^{[ 2 ]}${\displaystyle f}$${\displaystyle f}$${\displaystyle k}$${\displaystyle K_{f}^{k}}$

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

El lenguaje es creativo, con como su función productiva, porque cada programa en es mapeado por a un valor que es aceptado por (y por lo tanto también pertenece a ) o rechazado por (y por lo tanto tampoco pertenece a ). ^{[ 2 ]}${\textstyle 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}}$

Todo conjunto -creativo con una función productiva polinomialmente honesta es NP-completo. Para cualquier otro lenguaje en NP, por definición de NP, se puede traducir cualquier entrada para en un programa no determinista que ignora su propia entrada y en su lugar busca un testigo para , aceptando su entrada si la encuentra y rechazándola en caso contrario. La longitud de es polinomial en el tamaño de y se puede usar un argumento de relleno para que sea lo suficientemente largo (pero aún polinomial) para que su tiempo de ejecución califique para pertenecer a . ^{[ 2 ]}${\displaystyle k}$${\displaystyle X}$${\displaystyle x}$${\displaystyle X}$${\displaystyle p_{x}}$${\displaystyle x}$${\displaystyle p_{x}}$${\displaystyle x}$${\displaystyle p_{x}}$${\displaystyle \mathrm {NP} ^{(k)}}$

Sea la función productiva utilizada para definir un conjunto -creativo dado , y sea la traducción de a . Entonces, la composición de con mapea una entrada para el problema en una cadena que hace que el programa devuelva la respuesta incorrecta a la pregunta de si pertenece al complemento de . Cuando , el programa devolverá verdadero (independientemente del valor de ), por lo que para que esta respuesta verdadera sea incorrecta debe ser el caso que . Por el mismo razonamiento, cuando , . Por lo tanto, la composición de con es una reducción de muchos a uno en tiempo polinomial de a . Dado que es (por definición) en NP, y todo otro lenguaje en NP tiene una reducción a él, debe ser NP-completo. ^{[ 2 ]}${\displaystyle f}$${\displaystyle k}$${\displaystyle L}$${\displaystyle g}$${\displaystyle x}$${\displaystyle p_{x}}$${\displaystyle g}$${\displaystyle f}$${\displaystyle x}$${\displaystyle X}$${\displaystyle y=f(g(x))=f(p_{x})}$${\displaystyle p_{x}}$${\displaystyle y}$${\displaystyle L}$${\displaystyle x\in X}$${\displaystyle p_{x}}$${\displaystyle y}$${\displaystyle y\in L}$${\displaystyle x\notin X}$${\displaystyle y\notin L}$${\displaystyle g}$${\displaystyle f}$${\displaystyle X}$${\displaystyle L}$${\displaystyle L}$

La conjetura de Berman-Hartmanis afirma que existe un isomorfismo de tiempo polinomial entre dos conjuntos NP-completos cualesquiera: una función que mapea instancias "sí" de un conjunto a instancias "sí" del otro, de forma biyectiva, en tiempo polinomial, y cuya función inversa también puede calcularse en tiempo polinomial. Fue formulada por Leonard C. Berman y Juris Hartmanis en 1977, basándose en la observación de que todos los conjuntos NP-completos conocidos hasta entonces eran isomorfos. Una formulación equivalente de la conjetura es que todo conjunto NP-completo es rellenable . Esto significa que existe una transformación biyectiva de tiempo polinomial e invertible en tiempo polinomial de instancias a instancias equivalentes más grandes que codifican la información "irrelevante" . ^{[ 4 ]}${\displaystyle h(x,y)}$${\displaystyle x}$${\displaystyle y}$

Sin embargo, se desconoce cómo encontrar una transformación de relleno de este tipo para un lenguaje -creativo cuya función productiva no sea invertible en tiempo polinomial. 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. ^{[ 2 ]}${\displaystyle k}$${\displaystyle k}$

La conjetura de Joseph-Young (no probada) formaliza este razonamiento. La conjetura afirma que existe una función de longitud creciente unidireccional tal que no es rellenable. ^{[ 2 ]} 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 isomorfos. ^{[ 5 ]} Existe un oráculo con respecto al cual existen funciones unidireccionales, ambas conjeturas son falsas y la conjetura de Berman-Hartmanis es verdadera. ^{[ 6 ]}${\displaystyle f}$${\displaystyle K_{f}^{k}}$${\displaystyle f}$${\displaystyle \mathrm {SAT} }$${\displaystyle f(\mathrm {SAT} )}$