El problema P versus NP Stephen Cook

Universidad de TorontoOriginal: http://personales.ya.com/casanchi/mat/problema01.pdf

1. Planteamiento del problema El problema P versus NP es determinar si todos los lenguajes aceptados mediante algún algoritmo determinista en tiempo polinómico son también aceptados por

algún algoritmo (determinista) en tiempo polinomial. Para definir el problema precisamente es necesario para dar un modelo formal de un ordenador. La norma modelo de la computadora en la teoría de la computabilidad es la máquina de Turing, introducida por Alan Turing en 1936 [Tur36]. Aunque el modelo fue introducido antes con equipos físicos que fueron construidos, no obstante, sigue siendo aceptada como el modelo de equipo adecuado para el propósito de definir la noción de función computable.. Informalmente la clase P es la clase de problemas de decisión resolubles por algún algoritmo dentro de un número de pasos delimitados por algún polinomio fijo en la longitud de la entrada. Turing no se refiere a la eficiencia de sus máquinas, sino que su preocupación era saber si se pueden simular de forma arbitraria algoritmos de tiempo suficiente. Sin embargo resulta que las máquinas de Turing pueden en general, simular modelos informáticos más eficientes (por ejemplo máquinas equipadas con muchas cintas o una memoria ilimitada de acceso aleatorio) Por a lo sumo elevar al cuadrado o al cubo el tiempo de computación. Por lo tanto P es una clase robusta, y tiene definiciones equivalentes en una gran clase de modelos de computadora. Aquí seguimos con la práctica habitual y definimos los problemas de clase P en términos de máquinas de Turing. Formalmente los elementos de la clase P son lenguajes. Que sea Σ un alfabeto finito (Es decir, un conjunto no vacío finito) con al menos dos elementos, y dejar que Σ * el conjunto de cadenas finitas sobre Σ. Entonces un lenguaje sobre Σ es un subconjunto de L * Σ. Cada Máquina de Turing M tiene un alfabeto de entrada Σ asociada. Para cada cadena w en Σ * es un cálculo asociado a M con entrada w. (Las nociones de Máquina de Turing y la computación se definen formalmente en el apéndice.) Nosotros decimos que M acepta a w si este cálculo termina en el estado de aceptación. Nótese que M no acepta w si bien este cómputo termina en el rechazo estado, o si el cómputo no finaliza. El lenguaje aceptado por M, denotado L (M), se ha asociado alfabeto Σ y se define por

L (M) = {w ∈ Σ * | M acepta a w}

Indicamos por TM (w) el número de pasos en el cálculo de M en la entrada w (véase el Apéndice). Si este cálculo no se detiene nunca, a continuación, tM (w) = ∞. Para n ∈ se denota por TM(n) el tiempo del peor caso de ejecución de M, es decir

donde es el conjunto de todas las cadenas sobre Σ de longitud n. Decimos que M se

ejecuta en tiempo polinomial si existe k tal que para todo n, Ahora se define la clase P de lenguajes por

P = {L | L = L (M) por alguna máquina de Turing M que se ejecuta en tiempo polinomial}

La anotación NP significa "tiempo polinómico no determinista", ya que originalmente NP se define en términos de máquinas no deterministas (es decir, máquinas que tienen más de un posible movimiento de una configuración dada). Sin embargo, ahora se acostumbra a dar una definición equivalente, utilizando la noción

de una relación de cotejo, que es simplemente una relación binaria R ⊆ Σ * × Σ*1 para algunos alfabetos finitos s y s1. Nosotros asociamos con cada relación R LR un lengua sobre Σ ∪ Σ1 ∪ {#} definida por

LR = {w # y | R (w, y)}

donde el símbolo # no está en Σ. Decimos que R es de tiempo polinómico si y sólo si p ∈ LR Ahora definimos la clase NP de las lenguas por la condición de que una lengua L sobre Σ es en NP si y sólo si existe k ∈ N y una relación de cheques de tiempo polinómico R tal que para todo w ∈ Σ *,

w ∈ L ⇐ ⇒ ∃ y (| y | ≤ | w | k y R (W, Y))

donde | w | y | y | denota la longitud de W e Y, respectivamente.

Planteamiento del problema: ¿Es P = NP? Es fácil ver que la respuesta es independiente del tamaño del alfabeto Σ (Suponemos que | Σ | ≥ 2), ya que las cadenas sobre un alfabeto de cualquier tamaño fijo puede ser de manera eficiente las cadenas codificadas por más de un alfabeto binario. (Para | Σ | = 1 el problema está todavía abierto, aunque es posible que P = NP en este caso, pero no en el caso general.) Es trivial demostrar que P ⊆ NP, ya que para cada lenguaje L sobre Σ, si L ∈ P entonces podemos definir la relación de cheques de tiempo polinómico R ⊆ Σ * ∪ Σ * por

R (w, y) ⇐ ⇒ w ∈ L

para todo w, y ∈ Σ *.

Aquí hay dos ejemplos sencillos, utilizando la notación decimal para codificar los números naturales: El conjunto de cuadrados perfectos está en P y es el conjunto de números compuestos en NP (y no sabe que en P). Para estos últimos, el polinomio asociado tiempo de verificación relación R está dada por

R (a, b) ⇐ ⇒ 1 <b <a y b | a (1)

En general, la notación decimal de un número natural c se denota por c.

2. Historia e importancia La importancia de las preguntas P vs NP se deriva de las teorías exitosas de NP-completo y basado en la complejidad, la criptografía, así como la consecuencias prácticas potencialmente espectaculares de una prueba constructiva de P= NP. La teoría de NP-completo tiene sus raíces en la teoría de la computabilidad, que se originó en el trabajo de Turing, Church, Gödel, y otros en la década de 1930. Los precursores de computabilidad de las clases P y NP son las clases de decidible y c.e. (Computable enumerable) lenguajes, respectivamente. Nosotros decimos que un lenguaje L es c.e. (O semi-decidible) si y sólo si L = L (M) para algunos Máquina de Turing M. Nos dicen que la L es decidible si y sólo si L = L (M) para algunos de Turing máquina M que satisface la condición de que M se detiene en todas las cadenas de entrada w. Hay una definición equivalente de c.e. que pone de manifiesto su analogía con NP, a saber, L es c.e. si y sólo si hay una computable "la comprobación de la relación" R (x, y) tal que L = {x | ∃ YR (x, y)}. Usando la notación? M? para referirse a una cadena que describe una máquina de Turing M, definimos el HP problema de la parada de la siguiente manera:

HP = {? M? | M es una máquina de Turing que se detiene en la entrada M}? Turing usó un argumento diagonal sencillo para demostrar que HP no es decidible. Por otro lado, no es difícil demostrar que HP es ce De importancia central en la teoría de la computabilidad es la noción de reducibilidad, Turing, que se define más o menos de la siguiente manera: L1 se Alanguage Turing reducible si y sólo si a un lenguaje L2 hay una máquina de Turing M Oracle que acepta L1, donde M se le permite hacer consultas de los miembros de la forma x ∈ L2? que estén correctamente contestadas por un "oráculo" de L2. Más tarde, la noción más restringida de muchos-uno reducibilidad (≤ m) se introdujo y se define como sigue.

Definición 1: Supongamos que Li es un lenguaje de más de que

si existe una función computable total

tal que 1. Es fácil ver que si L1 ≤ m L2 y L2 es decidible, entonces L1 es decidible. Este hecho constituye una herramienta importante para mostrar la indecidibilidad, por ejemplo si HP L ≤ m entonces L es indecidible. La noción de NP-completo se basa en la noción de computabilidad siguiente teoría: Definición 2: L Alanguage se ce-completa si y sólo si L es ce, y L ≤ m L para todos los c.e. el lenguaje L. Es fácil demostrar que HP es c.e.-completo. Resulta más que "natural" indecidible c.e. las lenguas son, de hecho, c.e.-completo. Desde ≤ m es transitiva, para demostrar que un c.e. el lenguaje L es c.e. completa es suficiente para demostrar que

HP ≤ m L. La noción de la computación de tiempo polinómico se introdujo en la década de 1960 por Cobham [Cob64] y Edmonds [Edm65] como parte del desarrollo temprano de la teoría de complejidad computacional (aunque a principios de von Neumann [vN53] en 1953 la distinción entre tiempo polinomial y algoritmos de tiempo exponencial). Edmonds llama polinomio de algoritmos en tiempo "buenos algoritmos", y los vinculados a los algoritmos manejables. Ahora se ha convertido en un estándar en la teoría de la complejidad para identificar a tiempo polinómico con la posible, y aquí una digresión para discutir este punto. Es, por supuesto, no literalmente cierto que cada algoritmo de tiempo polinómico son factibles de ejecutar en las entradas pequeñas, por ejemplo un programa informático que requiere de pasos N100 podría 4 Nunca se ejecutará en una entrada, incluso tan pequeño como n = 10. Esta es una más declaración defendible (ver [Coo91]): Tesis de factibilidad: tiene un problema de Anatural posible algoritmo de si y sólo si tiene una tiempo polinómico del algoritmo. Ejemplos de problemas naturales que tienen tanto factible como polinomio de tiempo algoritmos abundan: la aritmética de enteros, álgebra lineal, el flujo de red, lineal de programación, muchos problemas de gráficos (conectividad, el camino más corto, mínimo árbol de expansión, coincidente bipartito), etc Por otro lado los resultados profundos de Robertson y Seymour [RS95] constituyen una fuente potencial de los contraejemplos con la tesis: Ellos demuestran que todas las familias de menor importancia-cerrada de los gráficos puede ser reconocidos en tiempo polinomial (de hecho en el tiempo O (n3)), pero los algoritmos suministrado por su método de tener tan grandes constantes que no son factibles. Sin embargo cada ejemplo contador potencial puede ser eliminado mediante la búsqueda de una posible algoritmo para ello. Por ejemplo, un algoritmo de reconocimiento factible es conocido por la clase de los grafos planos, pero ninguno se conoce actualmente para la clase de gráficos integrable en R3 con que no hay dos ciclos vinculados. (Ambos ejemplos son de menor importancia-cerrado las familias.) Por supuesto, las palabras "natural" y "viable" en la tesis anterior se debe explicar, en general, no consideramos una clase con un parámetro como naturales, tales como el conjunto de gráficos embebidos en una superficie de género k, k> 1. Mencionamos dos preocupaciones relacionadas con la dirección "sólo si" de la tesis. La primero viene de algoritmos aleatorios. Se discute al final de la sección 3 la posibilidad de que una fuente de bits aleatorios podría ser utilizado para reducir en gran medida el tiempo requerido para el reconocimiento algún lenguaje. Nótese sin embargo que no es

claro si una fuente verdaderamente al azar existe en la naturaleza. La segunda preocupación proviene de los ordenadores cuánticos. Este modelo incorpora la idea de equipo de la superposición de estados de la mecánica cuántica, y permite un potencial de exponencial de la velocidad de algunos cálculos sobre las máquinas de Turing. Por ejemplo, Shor [Sho97] ha demostrado que algunos algoritmo de la computadora cuántica es capaz de factores enteros en tiempo polinómico, pero no enteros en tiempo polinomial algoritmo de factorización es conocido por las máquinas de Turing. Sin embargo, los físicos tienen hasta ahora ha sido incapaz de construir un ordenador cuántico que puede manejar más de unos bits de media docena, por lo que esta amenaza a la viabilidad de la tesis es hipotética en presentar. Volviendo al tratamiento histórico de la teoría de la complejidad, en 1971 el 5 autor del presente artículo [Coo71] introdujo un concepto de NP-completos como polynomialtime analógica de c.e. certeza, excepto que la reducción utilizado fue un polinomio de tiempo análogo de la reducibilidad de Turing, más que de muchos-uno reducibilidad. Los principales resultados en [Coo71] es que varios problemas naturales, incluyendo Satisfacibilidad y 3-SAT (se define a continuación) y el isomorfismo subgrafo son NP-completos. ¡Ay del oído después Karp [Kar72] utiliza estos resultados integridad para demostrar que 20 problemas naturales son NP-completo, por lo tanto la fuerza demostrar la importancia de la materia. Karp también introdujo el Ahora notación estándar de P y NP y NP-completos redefinido con el polinomio de tiempo análogo de muchos-uno reducibilidad, una definición que se ha convertido en estándar. Mientras tanto, Levin [Lev73] independientemente de Cook y Karp se define la noción de "problema de la búsqueda universal", similar a NP-completo problema, y le dio seis ejemplos, entre ellos satisfacibilidad. Las definiciones oficiales sobre NP-completos son los análogos de cerca de Definiciones 1 y 2 anteriores. Definición 3: Supongamos que Li es un lenguaje de más de Σi, i = 1, 2. Entonces L1 L2 p ≤ (L1 es reducible a P-L2) si y sólo si existe una función computable en tiempo polinomial f: Σ * 2 tal que x ∈ L1 ⇐ ⇒ f (x) ∈ L2, para todo x ∈ Σ * Definición 4: L Alanguage es NP-completo si y sólo si L está en NP, y L p ≤ L para cada lenguaje L en NP. La siguiente proposición es fácil de demostrar: la parte (b) utiliza la transitividad de la ≤ p, y la parte (c) se sigue de la parte (a). Proposición 1: (a) Si L1 ≤ p L2 y L2 ∈ P entonces L1 ∈ P. (B) Si L1 es NP-completo, L2 ∈ NP, y L1 L2 ≤ p entonces L2 es NP-completo. (C) Si L es NP-completo y L ∈ P, entonces P = NP. Tenga en cuenta que las partes (a) y (b) tienen análogos en la teoría de la

computabilidad. analógica de la parte (c) es simplemente que si L es ce-completo entonces L es indecidible. La parte (b) es el método básico para mostrar nuevos problemas son NP-completo, y la parte (c) explica por qué es probable que sea una pérdida de tiempo buscando un polynomialtime algoritmo para un problema NP-completo. En la práctica un miembro de NP se expresa como un problema de decisión, y el 6 lenguaje correspondiente, se entiende el conjunto de cadenas de codificación SÍ instancias para el problema de la decisión por medio de técnicas de codificación. Así, el satisfacibilidad problema es: Dada una fórmula F proposicional, determinar si F es satisfacible. Para demostrar que esto es en NP se define el polinomio de tiempo comprobación de la relación R (x, y), que tiene si y sólo si x códigos de una fórmula proposicional F y códigos Y una asignación de verdad a las variables de F que hace F cierto. Este problema ha demostrado ser NP-completo en [Coo71] esencialmente por mostrando que para cada máquina M polinomio tiempo de Turing que reconoce una relación de cotejo R (x, y) para un lenguaje L NP, existe una polynomialtime algoritmo que toma como entrada una cadena x y produce un proposicional Fx fórmula (que describe el cálculo de M en la entrada (x, y), con variables en representación de la cadena y desconocido) de tal manera que es satisfacible si y sólo si Fx M acepta la entrada (x, y) para alguna y con | y | ≤ | X | O (1). Un caso especial importante de satisfactibilidad es 3-SAT, el cual también fue demostrado es NP-completo en [Coo71]. Los casos de 3-SAT están restringidos a las fórmulas en forma normal conjuntiva con tres literales por cláusula. Por ejemplo, el fórmula (P ∨ Q ∨ R) ∧ (PP ∨ Q ∨ ¯ R) ∧ (P ∨ Q ∨ ¯ S) ∧ (P ∨ ¯ ¯ ¯ R ∨ S) (2) es un sí a la instancia 3-SAT desde la asignación de verdad τ satisface la fórmula, , donde τ (p) = τ (Q) = True y τ (R) = τ (S) = False. Muchos cientos de problemas NP-completos han sido identificados, incluyendo SubsetSum (dado un conjunto de enteros positivos que se presentan en notación decimal, y una T de destino, ¿existe un subconjunto de sumar a T?), los problemas de muchos gráficos (Dado un grafo G, G tiene un ciclo de Hamilton? ¿Tiene G tienen una camarilla que consta de un medio de los vértices? ¿Pueden los vértices de G ser coloreado con tres

colores con colores distintos para los vértices adyacentes?). Estos problemas dan lugar a

muchos problemas de enrutamiento de la programación y con mayor importancia industrial. El libro [GJ79] proporciona una excelente referencia para el sujeto, con 300 NP-completo los problemas que figuran en el apéndice. Asociado con cada problema de decisión en NP existe un problema de búsqueda, que es, dada una cadena x, y encontrar una cadena de la satisfacción de la relación de cotejo R (x, y) para el problema (o determinar que x es un ejemplo NO al problema). Tal y se dice que es un certificado para x. En el caso de una NP-completo

problema es fácil ver que el problema de búsqueda puede ser eficientemente reducido 7 al problema de decisión correspondiente. De hecho, si P = NP entonces el asociado problema de búsqueda de todos los problemas NP tiene un algoritmo de tiempo polinómico. Para ejemplo, un algoritmo para la satisfactibilidad problema de decisión puede ser utilizado para encontrar una asignación de verdad τ la satisfacción de un F dado por la fórmula satisfacible, para cada variable P en F, a su vez, el establecimiento de P en True o False en F en F, que cada vez caso mantiene F satisfacible. El conjunto de complementos de lenguajes NP se denota CONP. El complemento de un lenguaje NP-completo no se cree que estar en NP, de lo contrario NP = CONP. El conjunto de tautologías TENSO (fórmulas proposicionales verdad en todas las tareas) es el ejemplo típico de un lenguaje CONP-completo. La conjetura de NP? CONP = es equivalente a la afirmación de que no sistema de prueba formal (convenientemente definida) para tautologías tiene corto (polynomialbounded) pruebas para todas las tautologías [CR79]. Este hecho ha motivado la desarrollo de una rica teoría de la complejidad a prueba proporcional [Kra95], una de cuyos objetivos es demostrar superpolynomial límites inferiores en las longitudes de pruebas para los sistemas estándar de prueba proposicionales. Hay ejemplos interesantes de los problemas NP que no se sabe que son, ya sea en P o NP-completo. Un ejemplo es el conjunto de números compuestos, que se menciona en

la primera sección, con relación de cotejo (1). Aquí se conjetura que hay hay reducción de tiempo polinómico de Turing del problema de búsqueda (entero factoring) para el problema de decisión. En concreto, Miller [Mil76] mostró cómo determinar en tiempo polinomial si un número dado es compuesto, en el supuesto la extendida hipótesis de Riemann, pero un número entero de factoring de tiempo polinómico algoritmo se cree probable que existan. De hecho, un eficiente algoritmo de factorización se rompería el esquema de cifrado de clave RSApublic [ARS78] de uso común para permitir que (presumiblemente) proteger las transacciones financieras a través de Internet. El complemento del conjunto de números compuestos (esencialmente el conjunto de primos) se ha demostrado ser en NP por un argumento interesante debido a Pratt [Pra75], y por lo tanto, es improbable que sea NP-completo. Existe un problema de decisión con NP equivalente a la de la complejidad entero el factoring, es decir, Lfact = {? A, b? | ∃ d (1 <d <a y d | b)} Dado un número entero b> 1, el menor divisor primo de B se puede encontrar con sobre las consultas de b log2 de Lfact, mediante la búsqueda binaria. Usando el teorema de Pratt, es 8 fácil ver que el complemento de Lfact también está en NP: un certificado que demuestre

? A, b? es una instancia no podría ser de Lfact la descomposición primer completa

de B, junto con los certificados de Pratt prueba de que cada uno de los factores primos es, en efecto principal. Por lo tanto, se considera poco probable que Lfact es NP-completo. Teoría de la complejidad computacional juega un papel importante en la criptografía moderna [Gol00]. La seguridad de la Internet, incluyendo la mayoría de las transacciones financieras, dependen de supuestos teóricos, tales como la complejidad de la dificultad de factoring entero o de romper DES (Data Encryption Standard). Si P = NP estas suposiciones son falsas. En concreto, un algoritmo de resolución de 3-SAT en pasos n2 podría ser utilizado para factorizar 200-dígitos en unos pocos minutos. A pesar de un algoritmo práctico para resolver un problema NP-completo (mostrando P = NP) tendría consecuencias devastadoras para la criptografía, lo haría También tienen impresionantes consecuencias prácticas de carácter más positivo, y no sólo por las soluciones eficientes a los muchos problemas NP-duros importantes a la industria. Por ejemplo, sería transformar las matemáticas, permitiendo una computadora para encontrar una prueba formal de un teorema que tiene una prueba de la razonable de longitud, ya que las pruebas formales pueden ser fácilmente reconocidas en el polinomio tiempo. Teoremas ejemplo bien puede incluir la totalidad de los problemas de CMI de los premios. A pesar de las pruebas formales no pueden ser inicialmente inteligible para los seres humanos, el problema de encontrar pruebas inteligibles se reduciría a la de encontrar un algoritmo de reconocimiento de pruebas inteligibles. Observaciones similares se aplican a diversos creativas actividades humanas, tales como el diseño de las alas del avión, la creación física teorías, o incluso la música componiendo. La cuestión en cada caso, es lo que medida en un algoritmo eficiente para el reconocimiento de un buen resultado se puede encontrar. Este es un problema fundamental en la inteligencia artificial, y cuya solución se se vería favorecida por la NP-solver al permitir que las pruebas de reconocimiento fácil teorías. Incluso si P? = NP todavía puede suceder que todos los problemas NP es susceptible a un algoritmo de tiempo polinómico que trabaja en "la mayoría" entradas. Esto podría hacer imposible la criptografía y llevar a cabo la mayor parte de los beneficios de un mundo en el que P = NP. Esto también motiva a la teoría de Levin [Lev86, Imp95] de integridad caso medio, en el que el P = NP cuestión se sustituye por la cuestión de si todos los problemas NP con cualquier probabilidad razonable distribución en sus entradas pueden ser resueltos en tiempo polinómico en promedio. En [Sma98] Smale muestra el P vs NP cuestión como un problema 3 de la matemática 9 problemas para el próximo siglo. Sin embargo Smale está interesado no sólo en el versión clásica de la cuestión, sino también una versión expresada en términos de el campo de los números complejos. Aquí las máquinas de Turing debe ser sustituido por un máquina modelo que es capaz de hacer aritmética exacta y pruebas cero en arbitrarias números complejos. El P vs NP cuestión se sustituye por una cuestión

relacionado con Nullstellensatz de Hilbert: ¿Existe un algoritmo de tiempo polinómico que, dado un conjunto de polinomios multivariados más de C k, determina si tienen un cero común? Ver [BCSS98] para un desarrollo de la complejidad La teoría en este entorno, incluyendo el resultado intrigante que el conjunto de Mandelbrot es indecidible. Los libros de Papadimitriou [] y Pap94 Sipser [Sip97] proporcionan buenas introducciones a la teoría de la corriente principal complejidad. 3. La conjetura y los intentos de demostrarlo La mayoría de los teóricos de la complejidad creer que P? = NP. Tal vez esto puede ser en parte explica por las consecuencias potencialmente espectaculares de P = NP mencionados anteriormente, pero hay mejores razones. Explicamos esto teniendo en cuenta los dos posibilidades, a su vez: P = NP y P = NP?. Supongamos primero que P = NP y considerar cómo se puede probar. Lo obvio manera es exhibir un algoritmo de tiempo polinómico para 3-SAT o una de la otra 1000 más o menos conocidos los problemas NP-completos, y de hecho muchas pruebas falsas ha presentado en este formulario. Hay un juego de herramientas estándar disponibles [CLR90] para la elaboración de algoritmos tiempo-polinomio, incluido el método codicioso, dinámica programación, la reducción a la programación lineal, etc Estas son las temas de un curso de algoritmos, típicas en las ciencias de la computación de pregrado planes de estudio. Debido a su importancia en la industria, un gran número los programadores de e ingenieros han tratado de encontrar algoritmos eficientes de problemas NP-completos en los últimos 30 años, sin éxito. Hay es así de fuerte motivación para romper los esquemas criptográficos que asumir la P? = NP por su seguridad. Por supuesto, es posible que algún argumento no constructiva, tales como el Roberton / Seymour pruebas se mencionó anteriormente, en relación con la viabilidad Tesis, podría demostrar que P = NP sin ceder ningún algoritmo posible para los estándares problemas NP-completos. Sin embargo en la actualidad la mejor probada límite superior de un algoritmo para la resolución de 3-SAT es de aproximadamente 1,5 n, donde 10 n es el número de variables en la fórmula de entrada. Supongamos por otro lado que P? = NP, y considerar cómo se podría lo demuestran. Hay dos métodos generales que se han probado: diagonalización / la reducción y el circuito booleano cotas inferiores. El método de reducción con diaonalization ha sido usado con mucho éxito en la teoría de la computabilidad para probar una serie de problemas indecidibles, a partir de con el problema de la parada. También se ha utilizado con éxito en la complejidad para probar la teoría de super-exponenciales límites inferiores de los problemas decidibles muy duros. Por ejemplo, Presburger aritmética, la teoría de primer orden de los números enteros bajo la suma, es una teoría decidible para el que Fischer y Rabin [FR74]

demostró que cualquier máquina de Turing para decidir la teoría debe utilizar por lo menos 22cn pasos en el peor de los casos, para un cierto c> 0. En general, los límites inferiores con diagonalización y la reducción de relativizar; que se siguen aplicando en un entorno en el que tanto la instancia de problema y la solución de máquina de Turing puede hacer

consultas de afiliación a un arbitrario conjunto de Oracle A. Sin embargo, en [BGS75] era demostrado que existe un oráculo conjunto A con respecto a la cual P = NP, lo que sugiere que diagonalización / reducción no se puede utilizar para separar estas dos clases. (No se nonrelativizing resultados en la teoría de complejidad, como se mencionó a continuación.) Es interesante observar que en relación con un genérico oráculo, P? = NP [BI87, SCY97]. Un circuito booleano es un gráfico acíclico finito en el que cada nodo no entrada, o puerta, se etiqueta con un conectivo booleano, por regla general de {Y, O, NO}. Los nodos de entrada están etiquetados con las variables x1, ..., xn, y para cada tarea de 0 o 1 a cada variable del circuito calcula un valor de bit en cada puerta, incluyendo la puerta de salida, de manera obvia. No es difícil ver que si L es un lenguaje sobre {0, 1} que está en P, entonces hay una familia polinomio de tamaño de Circuitos booleanos? BN? de tal manera que tiene n entradas Bn, y para cada cadena de bits w de longitud n, cuando w se aplica a los nodos de entrada de n Bn, entonces la salida poco de la BN es un si y sólo si w ∈ L. En este caso decimos que? BN? calcula L. Así, para demostrar que P? = NP es suficiente para demostrar una menor super-polinomial cota el tamaño de cualquier familia de circuitos booleanos para resolver algunos específicos NP-completo problema, tal como 3-SAT. En 1949 Shannon [Sha49] demostró que para casi todas las funciones f booleana: {0, 1} n → {0, 1}, cualquier f circuito de cálculo booleano requiere por lo menos 2n / n puertas. Desafortunadamente, su argumento no da cuenta pista en cuanto a la forma de demostrar cotas inferiores a los problemas en NP. Exponencial menor 11 los límites para los problemas NP se ha demostrado en los modelos de circuitos restringidos, incluyendo circuitos monótonos [Raz85, la AB87] y limitado en profundidad con los circuitos fan-in sin límites puertas [Has89, Smo87] (ver [BS90]). Sin embargo todos los intentos de para encontrar, incluso súper-lineales límites inferiores de libre disposición para los circuitos booleanos "Explícitamente" dadas las funciones de Boole se han encontrado con un fracaso total, el mejor ejemplo límite inferior demostrado hasta el momento se trata de 4n. Razborov y Rudich [RR97], explican este fallo, señalando que todos los métodos utilizados hasta ahora se pueden clasificar

como "pruebas naturales", y las pruebas físicas para los límites inferiores de circuitos generales están condenados al fracaso, asumiendo una cierta complejidad de la teoría de la conjetura afirmando que las fuertes pseudo-aleatorios generadores de números existen. Dado que tales generadores se han construido suponiendo que la dureza de la factorización entero, podemos inferir el sorprendente resultado de que una prueba natural para un general circuito límite inferior daría lugar a un algoritmo de factorización más eficiente lo que se conoce actualmente. El fracaso de la teoría de la complejidad de demostrar interés en cotas inferiores a un general modelo de cálculo es mucho más penetrante que la falta de prueba P? = NP. Es coherente con los conocimientos actuales que no sólo podía satisfacibilidad

tienen un algoritmo de tiempo polinómico, podría tener un algoritmo de tiempo lineal en una máquina de Turing multicinta. Lo mismo se aplica para todos los 21 problemas mencionado en el artículo original Karp [Kar72]. Hay separaciones complejidad de clase que sabemos que existen pero cannnot probar. Por ejemplo, considere la secuencia de inclusiones de clases de complejidad LOGSPACE ⊆ P ⊆ NP ⊆ PSPACE Arugment diagonal asimple muestra que el primero es un subconjunto propio de la durar, pero no podemos probar que se incluya al lado todo es correcto. Como otro ejemplo, vamos a LINEAL DE TAMAÑO ser la clase de lenguajes en {0, 1}

que puede ser calculada por una familia? BN? de circuitos booleanas de tamaño O (n). No se sabe si P o NP es un subconjunto de LINEAL DE TAMAÑO, a pesar de Kannan [Kan82] demostraron que hay lenguas en el polinomio jerarquía (una generalización de la NP), no en forma lineal-SIZE. Puesto que si P = NP a continuación, la jerarquía polinomial se colapsa para P, tenemos Proposición 2: Si P ⊆ LINEAR-SIZE, entonces P = NP?. Esta proposición podría ser interpretado como un método de la prueba de P? = NP, pero una creencia más común es que la hipótesis es falsa. 12 Pregunta Afundamen tal en teoría de la complejidad es la de si una fuente de azar bits se pueden usar para acelerar sustancialmente el reconocimiento de algunos lenguajes, siempre y cuando uno está dispuesto a aceptar una pequeña probabilidad de error. La clase AFF consta de todos los lenguajes L que puede ser reconocido por un estudio aleatorizado tiempo polinómico algoritmo, con un máximo de una probabilidad de error de forma exponencial pequeña en cada entrada. Por supuesto P ⊆ BPP, pero no se sabe si la inclusión es apropiado. El conjunto de los números primos está en BPP [SS77], pero no se sabe que en P. Areason para pensar que BPP = P es que algoritmos aleatorios a menudo se ejecuta con éxito utilizando un determinista pseudo-aleatorio generador de números como una fuente de "azar" bits. Hay una conexión indirecta pero intrigante entre las dos preguntas

P = BPP y P = NP. Sea E la clase de lenguajes reconocibles en tiempo exponencial, es decir la clase de lenguajes L tal que L = L (M) para una máquina de Turing M con TM (n) = O (2CN) para un cierto c> 0. Sea A el afirmación de que una lengua en E requiere la complejidad del circuito exponencial. Esto es Afirmación A: No existe L ∈ E y '> 0 tal que para cada familia de circuitos ? BN? computación L y para todo n suficientemente grande, Bn tiene al menos 2? n puertas. Proposición 3: Si A continuación, BPP = P. Si no es entonces P = NP?. La primera consecuencia es un teorema precioso al Impagliazzo y Wigderson [IW97] y la segunda es una observación interesante por lo que Kabanets V. fortalece la Proposición 2. En Kabanets hecho llega a la conclusión P? NP = a partir de una más débil suposición de que no A, es decir, que todas las lenguas en E puede ser calculado por una familia de circuitos booleana? BN? tal que para al menos una N, Bn tiene menos puertas que el máximo necesarios para calcular cualquier función de Boole f: {0, 1} n → {0, 1}. Pero no hay consenso sobre si esta hipótesis Es cierto. Cabe señalar que la Proposición 3 relativiza, y en particular en relación a cualquier aserción PSPACE-completa de Oracle A tiene y BPP = P = NP. Por lo tanto una construcción nonrelativizing será necesario si se quiere demostrar que P? = NP dando pequeños circuitos para los lenguajes en E. Sin embargo nonrelativizing construcciones se han utilizado con éxito antes, por ejemplo, en que muestra IP (Tiempo polinomial Interactive) contiene todos PSPSACE [Sha92]. En este y otras construcciones de este tipo es una técnica clave para representar funciones booleanas 13 por polinomios multivariados sobre cuerpos finitos. Anexo: Definición de máquina de Turing A urante M máquina consiste en un control de estado finito (es decir, un programa finito) unido a lectura / escritura de pasar una cinta infinita. La cinta se divide en cuadrados, cada uno capaz de almacenar un símbolo de un alfabeto finito Γ que incluye el símbolo b en blanco. Cada máquina tiene una M de entrada especificada Σ alfabeto, que es un subconjunto de Γ, sin incluir el símbolo b en blanco. A t cada paso de un cálculo de M es, en cierto q estado en un determinado conjunto finito Q

de estados posibles. Inicialmente, una cadena de entrada finita sobre Σ está escrito en la adyacente cuadrados de la cinta, todas las otras plazas están en blanco (contiene b), la cabeza escanea el símbolo más a la izquierda de la cadena de entrada, y M está en el estado inicial q0. E n cada paso M es, en cierto q el estado y la cabeza está escaneando un cuadrado de cinta que contiene algo de símbolo s cinta, y la acción realizada depende del par (q, s) y se especifica por la función de transición de la máquina (o programa) delta. La acción consiste en imprimir un símbolo en la plaza escaneada, moviéndose la cabeza hacia la izquierda o la derecha punto de partida, y suponiendo un nuevo estado.

Formalmente una máquina de Turing M es una tupla? Σ, Γ, Q, δ? , donde Σ, Γ, Q son finitos no vacío establece con Σ ⊆ Γ y b ∈ Γ - Σ. El conjunto estado Q contiene tres especial de los estados q0, qaccept, qreject.

La función de transición δ satisface δ: (Q - {qaccept, qreject}) × Γ → Q × Γ × {-1, 1} Si δ (q, s) = (q, s, h) la interpretación es que si M está en el estado q escanear el a continuación, símbolo s q es el nuevo estado, s es el símbolo impreso, y la cabeza de la cinta se mueve hacia la izquierda o la derecha un cuadrado en función de si h es -1 o 1. Suponemos que la Q series y Γ son disjuntos. Una configuración de M es una cadena con xqy x, y ∈ Γ *, no y la cadena vacía, y q ∈ P. La interpretación de la xqy configuración es que M está en el estado q con xy en su cinta, con su cabeza de exploración del símbolo más a la izquierda de y. Si C y C son configuraciones, después CM → C si C = xqsy y δ (q, s) = (Q, s, h) y tiene uno de los siguientes: C = xsqy y h = 1 e y es no vacío. 14 C = xsqb y h = 1 ey es vacío. C = xqasy yh = -1 y x = xa para algunos un ∈ Γ. C = qbsy y h = -1 y x es vacío. Xqy Aconfiguration se detendrá si q ∈ {qaccept, qreject}. Nótese que para cada nonhalting configuración de C hay una configuración única C de tal manera que CM → C. El cálculo de M en la entrada w ∈ Σ * es la única secuencia C0, C1, ... de configuraciones de tal manera que C0 = q0w (o C0 = q0b si w está vacía) y Ci M → Ci +1 para cada i con Ci +1 en el cálculo, y, o bien la secuencia es infinita o termina en una configuración de la detención. Si el cálculo es finito, entonces el número de pasos es uno menos que el número de configuraciones, de lo contrario el número de pasos es infinito. Decimos que M acepta w si y sólo si el cálculo es finito y la configuración final contiene el qaccept estado. Agradecimientos Mi agradecimiento a Avi Wigderson y Hugh Woodin para muchas sugerencias útiles para la mejora de una versión anterior de este artículo. Referencias [AB87] N. Alon y R. B. Boppana. La complejidad del circuito de la monótona funciones booleanas. Combinatorica, 7 (1) :1-22, 1987. [ARS78] L. Adleman, R. L. Rivest, Shamir y A.. Un método para obtener firma digital y criptografía de clave pública. Comunicación de la ACM, 21 (2), 1978. [BCSS98] L. Blum, F. Cucker, M. Shub y Smale S.. La complejidad y el Real Ciencia de la Computación. Springer-Verlag, Nueva York, 1998. [BGS75] T. Baker, J. Gill, y Solovay R.. Relativizaciones de la = P? NP cuestión. SICOMP: SIAM Journal on Computing, 1975. [BI87] M. Blum y R. Impagliazzo. Oráculos genéricos y clases de Oracle. En Ashok K. Chandra, editor, Actas del Simposio Anual 28a de Fundaciones de Ciencias de la Computación, páginas 118-126, Los

Ángeles, California, octubre de 1987. IEEE Computer Society Press. 15 [BS90] R. B. Boppana y Sipser M.. La complejidad de las funciones finitas. En J. Van Leeuwen, editor, Manual de Ciencias de la Computación Teórica, A Volumen: Algoritmos y Complejidad, páginas 759-804. Elsevier y The MIT Press, 1990. [CLR90] T. Cormen, Leiserson C. y R. Rivest. Introducción a los Algoritmos. McGraw Hill, Nueva York, 1990. [Cob64] A. Cobham. La dificultad intrínseca computacional de las funciones. En Yehoshua Bar-Hillel, editor, Actas de la Internacional de 1964 Congreso de Lógica, Metodología y Filosofía de la Ciencia, las páginas 24-30. Elsevier / North-Holland, 1964. [Coo71] Stephen Cook. La complejidad de los procedimientos de demostrar el teorema. Récord en la conferencia del Tercer Simposio Anual de ACM en la Teoría de de Informática, páginas 151-158, 1971. [Coo91] Stephen Cook. La complejidad computacional de las funciones de tipo superior. En Ichiro Satake, editor, Actas de la Internacional Congreso de Matemáticos, Kyoto, Japón, páginas 55-69. Springer-Verlag, 1991. [CR79] S. Cook y R. Reckhow. La eficiencia relativa de proposicional sistemas de prueba. J. Symbolic Logic, de 44 años (1), 1979. [] Edm65 Jack Edmonds. Mínimo de la partición de un matroide en independiente subconjuntos. Res. J.. Nat. Bur. Normas de la Secc. B, 69:67-72, 1965. [FR74] M. J. Fischer y M. O. Rabin. Super-exponencial de la complejidad Presburger aritmética. En R. M. Karp, editor, la complejidad de la computación, volumen 7, páginas 27-41. Sociedad Americana de Matemáticas, Providence, Rhode Island, 1974. [GJ79] M. R. Garey y D. S. Johnson. Las computadoras y Intractibility, un Guía para la Teoría de la NP-completo. W.H. Freeman and Co., San Francisco, 1979. [Gol00] Goldreich Oded. Los fundamentos de la criptografía-Volumen 1. Cambridge University Press, 2000. 16 [Has89] J. Hastad. Los límites inferiores de casi óptimo para los circuitos de poca profundidad. En S. Micali, editor, aleatoriedad y Computación, los avances en la Computing Research, vol. 5, páginas 143-170. JAI Press Inc., 1989. [Imp95] R. Impagliazzo. Ap ersonales vista de la complejidad del caso medio. 10 ª Conferencia Anual sobre la estructura IEEE en la Teoría de la Complejidad, páginas 134-147, 1995. [IW97] R. Impagliazzo y Wigderson A.. P = BPP si E requiere exponencial circuitos: Derandomizing el lema XOR. En COTS: ACM Simposio sobre Teoría de la Computación (COTS), 1997. [Kan82] Ravi Kannan. Tamaño del circuito, los límites inferior y reducibilidad no a la conjuntos dispersos. Información y Control, 55:40-56, 1982. [Kar72] Richard M. Karp. Reducibilidad de los problemas combinatorios. RE Miller y JW Thatcher, los editores, la complejidad de la Computación Cálculos, páginas 85-103, Nueva York, 1972. Plenum Press. [Kra95] J. Krajicek. Aritmética limitada, la lógica proposicional, y la complejidad

Teoría. Cambridge, 1995. [Lev73] L. Levin. Los problemas universales de la búsqueda (en ruso) ". Problemy Peredachi Informatsii, 9 (3) :265-266, 1973. Traducción de Inglés en Trakhtenbrot, BA: Una encuesta de los enfoques rusos Perebor (Fuerza bruta de búsqueda) algoritmos. Anales de la Historia de la computación, 6 (1984), páginas. 384-400. [Lev86] L. Levin. Caso medio problemas completos. SIAM J. Informática, 15:285-286, 1986. [Mil76] G. L. Miller. Hipótesis de Reimann y las pruebas de primalidad. J. Comput. Sistema Sci., 13:300-317, 1976. [Pap94] Christos Papadimitriou. Complejidad Computacional. Addison- Wesley, 1994. [Pra75] V. R. Pratt. Cada primer dispone de un certificado sucinto. SIAM Diario de Informática, 4 (3) :214-220, 1975. 17 [Raz85] Alexander A. Razborov. Los límites inferiores de la complejidad monótona de algunas funciones booleanas. Matemáticas Soviética. Dokl., 31:354-357, 1985. [RR97] Alexander A. Razborov Rudich y Steven. Las pruebas físicas. Revista de Ciencias de la Computación y Sistema, 55 (1) :24-35, agosto de 1997. [RS95] N. Robertson y P. D. Seymour. Menores de edad Gráfico I-XIII. Diario de Teoría Combinatoria B, 1983-1995. [SCY97] R. Impagliazzo S. Cook y Yamakami T.. Atigh t relación entre los genéricos y los oráculos de tipo-2 teoría de la complejidad. Información y Computación, 137 (2) :159-170, 15 de septiembre de 1997. [Sha49] C. Shannon. La síntesis de los circuitos de conmutación de dos terminales. Campana Técnico del Sistema Diario, 28:59-98, 1949. [Sha92] Adi Shamir. Ip = PSPACE. J.A.C.M., 39 (4) :869-877, de 1992. [Sho97] Peter Shor. Algoritmos tiempo-polinomio de descomposición en factores primos y los logaritmos discretos en un ordenador cuántico. 26:1484-1509, 1997. [Sip97] Michael Sipser. Introducción a la Teoría de la Computación. SPW, 1997. [Sma98] Steve Smale. Problemas matemáticos para el próximo siglo. MATHINT: El Mathematical Intelligencer, 20, 1998. [Smo87] R. Smolensky. Métodos algebraicos en la teoría de los límites inferiores de la complejidad del circuito booleano. En ACM Simposio sobre Teoría de la Informática (COTS), volumen 19, páginas 77-82, 1987. [SS77] R. Solovay y Strassen V.. AFAST de Monte-Carlo para la prueba de primalidad.

SIAM Journal on Computing, 6 (1) :84-85, marzo de 1977. [Tur36] Alan Turing. Sobre los números computables, con una solicitud a la entscheidnungsproblem. Proc. Londres Matemáticas. Soc.. servicios. 2, 42:230 - 265, 1936-7. 18 [VN53] J. von Neumann. Acertain de suma cero, juego de dos personas equivalentes para el problema de asignación óptima. En H. W. Kahn y W. A. Tucker, editores, Contribuciones a la Teoría de Juegos II. Princeton

Universidad. Press, 1953. 19