¿Existe una teoría de la complejidad análoga al teorema de Rice en la teoría de la computabilidad?

14

El teorema de Rice establece que cada propiedad no trivial del conjunto reconocida por alguna máquina de Turing es indecidible.

Estoy buscando un teorema del tipo Rice de teoría de la complejidad que nos indique qué propiedades no triviales de los conjuntos de NP son intratables.

Mohammad Al-Turkistany
fuente
Te pediría que aclararas un poco más, pero creo que sé a qué te refieres. La respuesta es esencialmente que el teorema de Rice todavía se aplica. Aunque no es la misma pregunta, creo que su pregunta está igualmente bien respondida por esto: cstheory.stackexchange.com/questions/161/… . Votación para cerrar como duplicado.
Joshua Grochow
1
Mi pregunta NO se trata de decidir el tiempo en que un conjunto está en NP, se trata de encontrar un teorema que pueda decir qué problemas en NP no son computables de manera eficiente (no tienen un algoritmo de tiempo polinómico).
Mohammad Al-Turkistany
66
¡Es demasiado pedir algo que pueda usarse para "probar" que un conjunto NP es intratable para resolver! Pero hay teoremas de Rice-ish que pueden usarse para establecer la "dureza NP" de los problemas.
Ryan Williams el
1
Joshua, déjame usar un ejemplo, el conjunto de gráficos de 3 colores está en NP. Quiero un teorema de estilo Rice que pueda usarse para demostrar que el problema de 3 colores no tiene ningún algoritmo de tiempo polinómico (probablemente intratable)
Mohammad Al-Turkistany
44
turkistany: estás pidiendo una prueba de que P! = NP? :) ¿O quieres decir que el algoritmo está restringido en algún sentido?
arnab

Respuestas:

38

Probar una versión teórica de tal complejidad del Teorema de Rice fue una motivación para mí para estudiar la ofuscación del programa.

El teorema de Rice dice, en esencia, que es difícil entender las funciones que los programas calculan, dado el programa. Sin embargo, la razón por la cual estos problemas son indecidibles es porque son infinitos. Incluso en una entrada, un programa puede no detenerse nunca, y debemos considerar lo que hace el programa en infinitas entradas.

Una versión finitaria del teorema de Rice fijaría el tamaño de entrada y el tiempo de ejecución de un programa, y ​​diría que el programa es difícil de entender. Una vez que haya solucionado estos problemas, puede ver el programa como un circuito booleano. ¿Qué propiedades de la función calculada por un circuito booleano son difíciles de calcular? Un ejemplo es `` no siempre 0 '', que son los problemas de Satisfacción NP-completa. Pero a diferencia del Teorema de Rice, hay algunas propiedades que no son triviales pero fáciles, incluso sin comprender el circuito. Siempre podemos saber eso: la función calculada por un circuito tiene una complejidad de circuito acotado (el tamaño del circuito). Además, siempre podemos evaluar el circuito en las entradas de nuestra elección.

fCn|C|fCnxxf(0..0)=1fC

Si bien esta pregunta está abierta hasta donde yo sé, se descartó nuestro enfoque previsto. Esperábamos demostrar esto demostrando que era posible ofuscar un programa criptográficamente seguro. Sin embargo, Booz demostró lo contrario: que era imposible. Esto muestra implícitamente que el acceso de caja negra a los circuitos es más limitado que el acceso completo a la descripción del circuito, pero la prueba no es constructiva, por lo que no puedo nombrar ninguna propiedad como la anterior que es fácil dada la descripción del circuito pero no con negro -caja de acceso. Es interesante (al menos para mí) si tal propiedad podría ser modificada por ingeniería de nuestro trabajo.

Aquí está la referencia: Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang: sobre la posibilidad (Im) de ofuscar programas. CRYPTO 2001: 1-18

Russell Impagliazzo
fuente
27

Se han demostrado varios de estos teoremas a lo largo de los años. Más recientemente, se han realizado esfuerzos para establecer teoremas de "estilo Rice" para problemas en circuitos. (Es natural reemplazar "máquinas" con "circuitos". Una vez que lo hace, el número total de entradas posibles se vuelve fijo, por lo que no tiene problemas de indecidibilidad). Dos referencias:

Bernd Borchert, Frank Stephan: buscando un análogo del teorema de Rice en la teoría de la complejidad del circuito. Matemáticas. Iniciar sesión. P. 46 (4): 489-504 (2000)

Lane A. Hemaspaandra, Jörg Rothe: un segundo paso hacia los análogos teóricos de la complejidad del teorema de Rice. Theor Comput Sci. 244 (1-2): 205-217 (2000)

Aquí hay un resultado de ejemplo: "Cada propiedad de contaje no vacía de los circuitos es UP-hard". Puede leer los documentos para obtener definiciones, pero esto significa aproximadamente que cualquier propiedad que dependa del número de asignaciones satisfactorias a un circuito es difícil para la clase UP (por lo tanto, intratable).

También hay trabajos anteriores sobre versiones teóricas de la complejidad del teorema de Rice, en una línea diferente. No estoy familiarizado con eso, pero los documentos anteriores los citan.

Ryan Williams
fuente
4

Un teorema de estilo Rice para nortePAGes el resultado probado por Hemaspaandra y Thakur que establece que cada propiedad de lenguaje no trivial denortePAG conjuntos es nortePAG-difícil.

Mohammad Al-Turkistany
fuente