¿Es la prueba de Norbert Blum de 2017 que

232

Norbert Blum publicó recientemente una prueba de 38 páginas de que . ¿Es correcto?PNP

También sobre el tema: ¿dónde más (en Internet) se está discutiendo su corrección?

Nota: el enfoque de este texto de pregunta ha cambiado con el tiempo. Vea los comentarios de las preguntas para más detalles.

Warren Schudy
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
Bjørn Kjos-Hanssen

Respuestas:

98

Como se señaló aquí antes, el ejemplo de Tardos claramente refuta la prueba; proporciona una función monótona, que concuerda con CLIQUE en T0 y T1, pero que se encuentra en P. Esto no sería posible si la prueba fuera correcta, ya que la prueba también se aplica a este caso. Sin embargo, ¿podemos señalar el error? Aquí está, de una publicación en el blog de Lipton, lo que parece ser el lugar donde falla la prueba:

El error único es un punto sutil en la prueba del Teorema 6, es decir, en el Paso 1, en la página 31 (y también 33, donde se discute el caso doble), una afirmación aparentemente obvia de que contiene todas las cláusulas correspondientes contenidas en , etc., parece incorrecto. C N F ( g )CgCNF(g)

Para explicar esto con más detalle, necesitamos entrar en el método de prueba y aproximación de Berg y Ulfberg, que reafirma la prueba original de Razborov de la complejidad monótona exponencial para CLIQUE en términos de interruptores DNF / CNF. Así es como lo veo:

Para cada nodo / compuerta de un circuito lógico (que contiene compuertas OR / AND binarias solamente), una forma normal conjuntiva , una forma normal disyuntiva y los aproximadores y son adjunto. y son simplemente las formas normales disyuntivas y conjuntivas correspondientes de la salida de la puerta. y también son formas disyuntivas y conjuntivas, pero de algunas otras funciones, "aproximando" la salida de la puerta. Sin embargo, se requiere que tengan un número limitado de variables en cada monomio paraβ C N F ( g ) D N F ( g ) C k g D r g C N F D N F D r g C k g D r g C k ggβCNF(g)DNF(g)CgkDgrCNFDNFDgrCgkDgr(menor que una constante r) y en cada cláusula para (menor que una constante k).Cgk

Existe la noción de un "error" introducido con esta aproximación. ¿Cómo se calcula este error? Solo estamos interesados ​​en algún conjunto T0 de entradas en el que nuestra función total toma el valor 0, y T1 de entradas en las que nuestra función total toma el valor 1 (una "promesa"). Ahora, en cada puerta, observamos solo las entradas de T0 y T1, que se calculan correctamente (tanto por como por , que representan la misma función: salida de la puerta en ) en la salida de la puerta , y mira cuántos errores / errores hay para yC N F ( g ) g β C k g D r g C k g D r g C k g C k g D r gDNF(g)CNF(g)gβCgkDgr, comparado con eso. Si la puerta es una conjunción, entonces la salida de la puerta podría calcular más entradas de T0 correctamente (pero las entradas calculadas correctamente de T1 posiblemente disminuyan). Para , que se define como una conjunción simple, no hay nuevos errores en todas estas entradas. Ahora, se define como un interruptor CNF / DNF de , por lo que puede haber una serie de nuevos errores en T0, provenientes de este interruptor. También en T1, no hay nuevos errores en : cada error debe estar presente en cualquiera de las entradas de compuerta, y de manera similar en , el interruptor no introduce nuevos errores en T1. El análisis para la puerta OR es dual.CgkDgrCgkCgkDgr

Por lo tanto, el número de errores para los aproximadores finales está limitado por el número de puertas en , multiplicado por el número máximo posible de errores introducidos por un interruptor CNF / DNF (para T0) o por un interruptor DNF / CNF (para T1). Pero el número total de errores tiene que ser "grande" en al menos un caso (T0 o T1), ya que esta es una propiedad de formas normales conjuntivas positivas con cláusulas delimitadas por , que fue la idea clave de la prueba original de Razborov (Lemma 5 en el periódico de Blum).kβk

Entonces, ¿qué hizo Blum para lidiar con las negaciones (que se empujan al nivel de las entradas, por lo que el circuito todavía contiene solo puertas binarias OR / AND)?β

Su idea es preformar los conmutadores CNF / DNF y DNF / CNF de manera restrictiva, solo cuando todas las variables son positivas. Entonces los interruptores funcionarían EXACTAMENTE como en el caso de Berg y Ulfberg, introduciendo la misma cantidad de errores. Resulta que este es el único caso que debe considerarse.

Entonces, sigue las líneas de Berg y Ulfberg, con algunas distinciones. En lugar de adjuntar , , y a cada puerta del circuito , adjunta sus modificaciones, , , y , es decir, las formas normales disyuntivas y conjuntivas "reducidas", que definió como diferentes de yD N F ( g ) C k g D r g g β C N F ( g ) D N F ( g ) C k g D r g C N F ( g ) D N F ( g ) C r g D rCNF(g)DNF(g)CgkDgrgβCNF(g)DNF(g)CgkDgrCNF(g)DNF(g)por "regla de absorción", eliminando variables negadas de todos los monomios / cláusulas mixtas (también utiliza para este propósito la operación indicada por R, eliminando algunos monomios / cláusulas por completo; como discutimos antes, su definición algo informal de R no es realmente el problema , R se puede precisar para que se aplique en cada puerta, pero lo que se elimina depende no solo de las dos entradas anteriores, sino de todo el circuito que conduce a esa puerta), y sus aproximadores y , que él también presentó.CgrDgr

Concluye, en el Teorema 5, que para una función monótona, la reducción de y realmente calculará 1 y 0 en los conjuntos T1 y T0, en el nodo raíz (cuya salida es la salida de toda la función en ). Este teorema es, creo, correcto. D N F g 0 βCNFDNFg0β

Ahora viene el conteo de errores. Creo que los errores en cada nodo deben calcularse comparando y reducidos (que ahora son posiblemente dos funciones diferentes), a y como él los definió. Las definiciones de los aproximadores definen las definiciones de y (Paso 1) al mezclar variables con las negadas, pero cuando trata con variables positivas, usa el interruptor como en el caso de Berg y Ulfberg (Paso 2). Y, de hecho, en el Paso 2 introducirá la misma cantidad de posibles errores que antes (es el mismo interruptor y todas las variables involucradas son positivas).D N F ( g ) C r g D k g C N F D N F CNF(g)DNF(g)CgrDgkCNFDNF

Pero la prueba es incorrecta en el Paso 1. Creo que Blum confunde , , que realmente proviene, tal como los definió, de aproximadores anteriores (para puertas , ), con partes positivas de y . Hay una diferencia, y por lo tanto, la declaración " contiene todavía todas las cláusulas contenidas en antes de la aproximación de la puerta g que usa una cláusula en o " parece ser mal en general.γ 2 h 1 h 2 C N F β ( h 1 ) C N F β ( h 2 ) C g C N F β ( g ) γ 1 γ 2γ1γ2h1h2CNFβ(h1)CNFβ(h2)CgCNFβ(g)γ1γ2

idolvon
fuente
2
parece ser el mismo comentario en el blog RJL rjlipton.wordpress.com/2017/08/17/…, ¿ escribiste eso? quería agregar una idea: ¿qué pasa si la clave es considerar T0 / T1 de todos los 1 bits wrt cnf-dnf conversión / aproximación? es conocido por Berkowitz 1982, esto es suficiente para separar P vs NP ver "complejidad de las funciones de corte" / wegener sciencedirect.com/science/article/pii/0304397585902099
vzn
66
@vzn El autor de este comentario en el blog es "vloodin". El autor de esta respuesta es "idolvon". Una permutación de las letras da una pista de que los autores no son muy diferentes.
Clement C.
2
Solo por curiosidad, ¿ha habido algún tipo de comunicación pública adicional de Blum después de subir el periódico al arxiv?
Matt
99
@Matt Blum se retractó del documento y publicó el siguiente comentario en la página arXiv del documento: "La prueba está equivocada. Elaboraré con precisión cuál es el error. Para hacer esto, necesito algo de tiempo. Pondré la explicación en mi página de inicio "
Gustav Nordh
Esta respuesta ha sido confirmada como correcta por Scott Aaronson, citando a otros revisores (sin nombre): scottaaronson.com/blog/?p=3409
cuniculus
95

Estoy familiarizado con Alexander Razborov, cuyo trabajo previo es extremadamente crucial y sirve como base para la prueba de Blum. Tuve la suerte de conocerlo hoy y no perdí el tiempo en pedirle su opinión sobre todo este asunto, sobre si había visto la prueba o no y cuáles son sus pensamientos al respecto si lo hizo.

Para mi sorpresa, él respondió que realmente estaba al tanto del papel de Blum, pero no le importó leerlo inicialmente. Pero a medida que se le dio más fama, tuvo la oportunidad de leerlo y detectó una falla de inmediato: a saber, que los razonamientos dados por Berg y Ulfberg se ajustan perfectamente a la función de Tardos, y dado que esto es así, la prueba de Blum es necesariamente incorrecto ya que contradice el núcleo del Teorema 6 en su artículo.

Mikhail
fuente
2
Sería genial si pudieras dar más detalles sobre esto. ¿Se sabe que la función de Tardos está en P?
Thomas
55
La función de Tardos está en P, y es una aproximación de la función thevas de thevas, que, para un complemento gráfico, está entre el número de camarilla y el número cromático. La función real de Lovasz theta es la función monótona de un gráfico. Sin embargo, la pregunta es si esta aproximación da lugar a una función monótona de un gráfico también (solo la función monótona invalidaría la prueba). ¿Puede alguien darnos la referencia al documento de Tardos donde se define esto, por favor?
idolvon
77
@idolvon Quiere decir esto: cs.cornell.edu/~eva/… Establece explícitamente que la función φ es una función monótona computable de tiempo
múltiple
12
¡Gracias! Eso básicamente lo resuelve: la prueba de Bloom debe estar equivocada. Ahora, puede ser interesante señalar un error. Lo investigaré y publicaré un comentario en Lipton's, como en los viejos tiempos, según el profesor. p Deseos del pájaro carpintero.
idolvon
1
@idolvon Sí, yo también lo pensé. Los argumentos de Blum deben trasladar la función φ como se define en ese documento que establece que es monótono y polimetálico computable (trivial por su definición).
PsySp
41

Esto se publica como respuesta de la comunidad porque (a) no son mis propias palabras, sino una cita de Luca Trevisan en una plataforma de redes sociales o de otras personas sin cuenta CSTheory.SE; y (b) cualquiera debería sentirse libre de actualizar esto con información actualizada y relevante.


Citando a Luca Trevisan de una publicación pública de Facebook (14/08/2017), respondiendo a una pregunta sobre este documento hecha por Shachar Lovett :

La función de Andreev, que se afirma que tiene una complejidad de circuito superpolinomial (resumen, luego sección 7), es solo una interpolación polinómica univariada en un campo finito que, si no me falta algo, se puede resolver mediante la eliminación gaussiana

En realidad, este no es necesariamente un punto donde la prueba falla; Luego, Luca respondió lo siguiente (15/08/2017), después de una pregunta relacionada con el comentario de Andrew a continuación:

Tienen razón, muchachos, no entendí bien la definición de la función de Andreev: no está claro que se reduzca a la interpolación polinómica


Karl Wimmer comentó sobre el punto planteado por Gustav Nordh (reproducido con el permiso de Karl):

DNF(g0)fDNF(g0)f=1

DNF(g0)fDNF(g0)f

(Aparte: esta unilateralidad es consistente con el ejemplo anterior de Gustav ).

DNF(g)gDNF(g0)

Si estoy totalmente fuera de lugar aquí, ¡házmelo saber!


De un usuario anónimo, en reacción al punto de Karl:

DNF 'y CNF' son solo DNF y CNF para f, en el que se realizan cancelaciones de literales opuestos, reduciéndolos así a una forma más corta. Esto también se explica en el documento, y es algo engorroso desde la definición, pero eso es lo que es. El teorema 5 no es el problema, la carne está en el teorema 6.


Y la respuesta de Karl (que reproduzco nuevamente aquí):

fg0DNF(g0)RDNF(g0)fDNF(g0)

RDNF(g0)gDNF(g)gres(g)

RαR


(respuesta de anon) Estoy de acuerdo en que la vaguedad en la definición de R podría ser un problema en la sección 6. R no está explícitamente definido, y a menos que su acción dependa de alguna manera del DNF completo (y no de los valores de DNF 'en las puertas inductivamente) , puede haber un problema La prueba de Deolalikar tuvo un problema similar: se confundieron dos definiciones diferentes. Aquí, al menos sabemos qué significa DNF ', y si este es el origen del problema en la sección 6, puede ser fácil de rastrear. Sin embargo, aún no entré en la sección 6, requiere la comprensión de la prueba de los aproximadores de Berg y Ulfberg descritos en la sección 4, en última instancia relacionada con la construcción de Razborov de 1985, lo que no es fácil.

Explicación de cómo funciona R:

(xy)(¬xy)(x¬y)
((xy)(¬xy))(x¬y)
(xy)((xy)(yy))
x
(y)(xy)(y),
yx
((y)(xy)(y))((xy)(xy)(xy)),
((xy)(xy)(xy))
(xy)
Clemente C.
fuente
66
Soy escéptico sobre esto (pero no use Facebook para decir nada allí): la función de Andreev (en el documento) se presenta como un gráfico bipartito con conjuntos de vértices izquierdo y derecho iguales a GF (q), más un conjunto de bordes arbitrario , y un grado limitado. La pregunta es si hay una manera de elegir, para cada vértice de la izquierda, uno de sus vecinos, de modo que la función inducida (de izquierda a derecha) sea un polinomio de bajo grado. El comentario de Luca se aplica una vez que tenemos una buena opción de vecino para cada vértice izquierdo (ya que es solo una interpolación polinómica), pero no me queda claro cómo hacer una buena elección.
Andrew Morgan
@ AndrewMorgan Actualicé la respuesta de CW.
Clement C.
@Karl Wimmer: con respecto al clima DNF ′ (g0) calcula f, uno necesita usar que f es monótono, creo. Se supone en el Teorema 5 que f es monótono.
idolvon
¡confuso! ¿Esto es todo cita de la publicación de Facebook? Al hacer clic en el enlace de Facebook de shachar lovett arriba, algunas de las respuestas anteriores son visibles para mí, pero otras no son visibles para mí. por ejemplo, Karl Wimmer. ¿Es esto debido a una selección de respuestas de amigos en Facebook? Si es así, esto es decepcionante y no es un muy buen lugar para la discusión pública. tal vez alguien puede hacer una captura de pantalla? :( o ¿estás citando cosas de fuera de la publicación de Facebook? por favor ten cuidado / completa con citas / urls
vzn
¡Oh! investigación adicional también está citando respuestas de la publicación de blog de baez que contiene la respuesta de Wimmers,
vzn
36

La exactitud de la prueba reclamada se está discutiendo en el blog de Luca Trevisan: https://lucatrevisan.wordpress.com/2017/08/15/on-norbert-blums-claimed-proof-that-p-does-not-equal- notario público/

En particular, "anon" publicó el siguiente comentario relevante:

"Tardos observó que los argumentos de Razborov y Alon-Boppana se trasladan a una función que se calcula mediante un circuito no monótono de tamaño polinómico (la función es una pequeña variante para aproximar la función thevas de Lovasz del gráfico). Si los argumentos de Berg y Ulfberg también solicite la función de Tardos (que es intuitivamente probable, ya que su prueba parece estar basada en la prueba de Razborov), entonces está claro que la afirmación actual de Blum no puede ser correcta. Desafortunadamente, el autor no discute este punto ".

Sobre una pregunta directa de "Mikhail", Alexander Razborov confirma esto (ver la publicación de Mikhail): los razonamientos dados por Berg y Ulfberg se mantienen perfectamente para la función de Tardos, y dado que esto es así, la prueba de Blum es necesariamente incorrecta ya que contradice el núcleo del sexto teorema en su artículo. - A. Razborov

En mi opinión, esto definitivamente resuelve la cuestión de si el documento es correcto o no (¡NO es correcto!). También es importante tener en cuenta que parece difícil reparar la prueba, ya que el método de prueba en sí parece defectuoso.

Actualización (30/08/2017) Norbert Blum publicó el siguiente comentario en su página arXiv:

La prueba está mal. Explicaré con precisión cuál es el error. Para hacer esto, necesito algo de tiempo. Pondré la explicación en mi página de inicio

Gustav Nordh
fuente
3
Publiqué esto como respuesta ya que aún no tengo privilegios para publicar comentarios.
Gustav Nordh
11
Sí, este es mi entendimiento (pero puedo estar equivocado). La función de Tardos es una función monótona que es 1 en k-cliques y 0 en gráficos completos (k-1) -partitos. Por lo que puedo decir, Berg y Ulfberg SÓLO usan estas propiedades en su prueba de aproximación CNF-DNF para CLIQUE, lo que demuestra que la función de Tardos tiene una complejidad monótona exponencial. El Teorema 6 de Blum dice que los límites inferiores de la complejidad monótona por aproximación CNF-DNF para funciones monótonas, dan el mismo límite inferior NO monótono. Por lo tanto, la función de Tardos tiene una complejidad exponencial según el Teorema 6 (que es falso).
Gustav Nordh
55
En ese caso, parece que resolver este punto debería ser un enfoque principal en este momento ... No creo que sea competente o lo suficientemente informado como para hacerlo, pero (los dedos cruzados, lo que no ayuda a escribir) otros lo son.
Clement C.
3
¿Dónde se define esta función de Tardos? ¿Alguien puede hacer referencia al artículo? Claramente, existen funciones no monótonas que separan T0 y T1 que están en P (es fácil de construir, por ejemplo, verificando si tenemos un gráfico completo con k nodos), pero ¿la función de Tardos es monótona? Si es monótono y separa T0 y T1, invalidaría la prueba. Pero si no es monótono, entonces la prueba aún podría ser correcta.
idolvon
44
La función de Tardos se define en su breve artículo ubicado aquí: cs.cornell.edu/~eva/… Además, las propiedades de la función de Tardos se analizan en detalle en [S. Jukna, Complejidad de la función booleana p. 272]
Gustav Nordh
25

Gustav Nordh comentado por el Teorema 5 (página 29). Específicamente, la función

(xy)(¬xy)(x¬y)

1xy1βxyβg0

DNFβ(g0)β

xy(xy)

DNFβ(g0)fDNFβ(g0)xfx=1f(x,y)=1R

kdog
fuente
2
Parece que DNF 'para esta fórmula es (
xY
2
DNF
2
La definición en las páginas 27-28 implica el uso del operador R, que no está definido excepto por la vaga frase "se origina en un monomio trivial". Si tomamos eso como "se cancelaría si los literales se mantuvieran hasta esta etapa", entonces las definiciones son las mismas. En cualquier caso, necesitaría ALGUNA interpretación para R. Dado que R es tan crucial en el capítulo 6, la interpretación correcta es importante, y de hecho hay una que es inductiva.
idolvon
2
(xy)(¬xy)(x¬y)
((xy)(¬xy))(x¬y)
(xy)((xy)(yy))
x
(y)(xy)(y),
2
yx
((y)(xy)(y))((xy)(xy)(xy)),
((xy)(xy)(xy))
(xy)
17

¿Se podría usar la decodificación de listas de los códigos Reed-Solomon para mostrar que la función POLY de Andreev está en P, de forma similar a como lo hizo Sivakumar en su trabajo comparable de membresía ? ¿O se sabe que la función POLY es NP-completa?

Lance Fortnow
fuente
10
Lance, no respondo a tus preguntas. En junio de 1986, el "Problema abierto del mes" de David Johnson preguntó si el problema de Andreev es NP completo. Ver la columna de integridad NP de David en el Journal of Algorithms 7: 2, pp. 289-305. No estoy seguro si alguna vez hubo una resolución.
Ravi Boppana
1
El artículo de Johnson de 1986 es anterior a las técnicas de reconstrucción polinómica y los resultados de decodificación de listas de los años 90.
Lance Fortnow
1
Aquí está mi idea usando la notación en la Sección 7 del artículo de Norbert Blum. Un polinomio p que es una solución al problema POLY podría verse como una palabra clave de Reed-Solomon. Elija una función f eligiendo aleatoriamente una arista de cada vértice en A. Esa f debería coincidir con p en significativamente más de una fracción 1 / q de las entradas. Entonces podemos usar la decodificación de listas en f para crear una lista polinomialmente larga de posibilidades para p y podemos verificar cada una de ellas.
Lance Fortnow
1
qddpdqlogq1q
44
@Matt Suponiendo que leí lo anterior correctamente, esa función es la única Blum para la cual se afirma que ha probado la complejidad del circuito superpolinomial. Pero si está en P, debe tener una complejidad de circuito polinomial, lo que contradice la supuesta prueba de P frente a NP.
Clement C.
14

Ha actualizado su arXiv para decir que su prueba es incorrecta:

La prueba está mal. Explicaré con precisión cuál es el error. Para hacer esto, necesito algo de tiempo. Pondré la explicación en mi página de inicio.

Mehrdad
fuente
9

El blog de Lipton y Regan aquí tiene una buena discusión de alto nivel con un comentario interesante sobre la estructura de la prueba.

También señalan que el pedigrí de Blum ha demostrado ser un límite inferior en la complejidad del circuito booleano que se mantuvo durante más de 30 años. Por supuesto, esto es solo "información secundaria" ya que los expertos ya están estudiando seriamente la prueba.

kodlu
fuente
3

Además, aquí: https://www.quora.com/Whats-the-status-of-Norbert-Blums-claim-that-operatorname-P-neq-operatorname-NP

Citando a Alon Amit:

(opinión personal, 14 de agosto, más adelante en el día): No creo que este documento resista el escrutinio. Un teorema profundo que ha sido investigado de forma masiva como P P NP, con toda probabilidad, se resolverá con nuevas técnicas profundas y de largo alcance. No es imposible que se resuelva con una ligera mejora de los métodos existentes y conocidos, pero es muy, muy, muy poco probable.

Jack
fuente
11
Eso es un no argumento (una opinión válida, y una que admito que comparto, pero no un argumento válido, que es lo que creo que deberíamos tener aquí). Este tipo de cosas ha sucedido antes .
Clement C.
8
Sí, no estaba discutiendo nada. Simplemente responda la pregunta "¿dónde se discute este documento?", Y luego resuma dicha discusión hasta este punto.
Jack
2

Es poco probable que sea correcto por la siguiente razón: el método de aproximaciones es lo suficientemente general como para que pueda probarse cualquier límite inferior con ellos. Este es un resultado debido a Razborov. Por qué es un problema? Debido a que significa que el método de aproximaciones no será el progreso principal, puede expresar cualquier cosa, la carne estará en otro lugar. No parece haber tanta carne en el documento, lo que sugiere que lo más probable es que el autor esté cometiendo un error sutil, el tipo de error que se oculta a los ojos, pero esencialmente es una suposición que implica la respuesta. Para aquellos que no son teóricos de la complejidad: esta es una muy buena prueba de olor, es tan cierto como la afirmación de alguien de construir un cohete en su sótano para viajar a la luna en una semana.

Entonces, ¿dónde está ese error sutil? En el blog de Trevisan hay un comentario de Lovett que sugiere cuál podría ser esa suposición oculta en el teorema 6.

Escéptico
fuente
punto agradable / relevante; fyi razborovs "no va", "está en el método de aproximaciones" (1989) people.cs.uchicago.edu/~razborov/files/approx.pdf pero siente que esta prueba no está muy bien analizada. Uno tiene que entender cuidadosamente si sus condiciones establecidas van más allá de las palabras "método de aproximaciones" que ha pasado por revisiones / desarrollos / refinamientos, etc. desde su origen por razborov. aparentemente estas condiciones exactas no son muy analizadas por investigadores posteriores. la otra barrera importante es por razborov / rudich pruebas naturales en.wikipedia.org/wiki/Natural_proof
vzn
rechazado porque el contenido de esta respuesta ya se abordó en respuestas anteriores.
verificar el
-2

NPcP

CffCm

Una función booleana tiene una sola tabla de verdad pero no una sola expresión algebraica, ni un problema tiene una sola función booleana que la resuelva.

Algunas (pueden ser todas) las funciones son isomórficas (los problemas no lo son).

NP=Pmmfff

Ixer
fuente