Dureza de las funciones booleanas ruidosas

13

Sea una función booleana de n variables booleanas. Sea g ( x ) = T ϵ ( f ) ( x ) el valor esperado de f ( y ) cuando y se obtiene de x al voltear cada coordenada con probabilidad ϵ / 2 .fng(x)=Tϵ(f)(x)f(y)yxϵ/2

Estoy interesado en casos en los que es computacionalmente difícil aproximar . Permítanme fijar una noción de "aproximación" (pero puede haber otras): una función booleana h se aproxima a g si h ( x ) = 1 cuando g ( x ) 0.9 y h ( x ) = 0 cuando g ( x ) 0.1ghgh(x)=1g(x)0.9h(x)=0g(x)0.1Un argumento de conteo (basado en la existencia de códigos de corrección de error de tasa positiva) parece dar que existen funciones booleanas para las cuales dicha aproximación requiere un circuito de tamaño exponencial. Pero la pregunta es qué sucede cuando para comenzar es en NP o en su vecindario.f

P1: ¿Hay un ejemplo de descrito por el circuito NP (o espacio P) de modo que cada h sea ​​NP duro, o difícil en algún sentido más débil.fh

Para ver que no siempre será fácil (Doy gracias a Johan Håstad útil para el debate al respecto) podemos considerar la propiedad de los gráficos de tener una camarilla de tamaño n 1 / 4 , para la entrada al azar, es concebible que es difícil detectar si hay una camarilla grande pero esto se manifiesta al tener camarillas de tamaño más grandes de lo esperado en el gráfico ruidoso. En este caso, cualquier h será probablemente difícil (pero no demostrable, y no terriblemente difícil como lo dirán los circuitos cuasi-polinomiales).hn1/4h

P2: ¿Cuál es la situación si para comenzar es de baja complejidad? ( A C 0 , monótono T C 0 , A C C etc.)fAC0TC0ACC

P3: ¿Cuál es la situación para algunos ejemplos básicos de funciones booleanas? (La pregunta puede extenderse también a la función de valor real).

P4: ¿Se puede hacer formalmente la pregunta anterior para el modelo de computación uniforme (máquina de Turing)?

Actualización: En vista de la respuesta de Andy (Hola, Andy), creo que la pregunta más interesante es comprender la situación de varias funciones específicas.

Actualizar Otra pregunta Q5 [Q1 para funciones monótonas] (también en vista de la respuesta de Andy). ¿Cuál es la situación si es monótono? ¿Podemos codificar de manera sólida las preguntas completas de un NP>f

Gil Kalai
fuente
En mi opinión, esta pregunta sobre la aproximación de circuitos está relacionada. su pregunta parece ser similar a la pregunta P / poli vs NP.
vzn

Respuestas:

14

para la Pregunta 1, la respuesta es Sí, y se puede mostrar de la siguiente manera. (También esbozaré implícitamente una respuesta afirmativa a la P4, ya que el argumento es uniforme y tratará todas las longitudes de entrada a la vez).

Repare cualquier lenguaje completo de NP y una familia de buenos códigos binarios de corrección de errores (con tasa 1/4 y corrección de una fracción de errores .1, por ejemplo). Sea E n c n : { 0 , 1 } n{ 0 , 1 } 4 n sea ​​la función de codificación para la longitud n ; usamos un código de este tipo donde E n c = { E n c n } es computable por un algoritmo de tiempo polinómico uniforme.LEncn:{0,1}n{0,1}4nnEnc={Encn}

Defina como el conjunto de cadenas z que están dentro de la distancia como máximo .05 | z | a partir de una palabra de código y E n c ( L ) que codifica algún elemento de L . Tenga en cuenta que L ' está en NP, como se puede adivinar y comprobar la palabra de código de cerca, la palabra descodificada, y el certificado de NP para ser miembro de la palabra decodificada en L . Lz.05|z|yEnc(L)LLL

Entonces la afirmación es que cualquier "aproximación" de en su sentido es NP-difícil para ε = .01 . Si consideramos una palabra de código válida y = E n c ( x ) de cierta longitud 4 n , entonces con probabilidad 1 - o ( 1 ) sobre una versión aleatoria ε- perturbada y ' de y , no estará de acuerdo con y como máximo una fracción de .05 de coordenadas, y por lo tanto no estará de acuerdo con cualquier otra palabra de código de E n cLε=.01y=Enc(x)4n1o(1)εyyy en unafracción demás de 0,05 de coords. Para tales y ' tenemos y 'L ' si y sólo si x L . Entonces, si h es una aproximación a laversión ε- suavizada de L ' en su sentido, entonces debemos tener h ( y ) = L ( x ) . Como E n c es eficientemente computable, esto nos da una manera de reducir eficientemente las preguntas de membresía de L a las de h . EntoncesEncn.05yyLxLhεLh(y)=L(x)EncLh es NP-duro.h

Dos notas:

(1) las codificaciones de corrección de errores de instancias de NP se han utilizado anteriormente en varios documentos, en particular
D. Sivakumar: sobre conjuntos comparables de miembros. J. Comput. Syst. Sci. 59 (2): 270-280 (1999).

(2) el argumento anterior, por supuesto, no dice nada acerca de la complejidad del caso promedio de cualquier problema de NP, ya que la corrección de errores se aplica caso por caso.

Andy Drucker
fuente
8
El software no me permite comenzar mi respuesta con "Hola Gil", y este nivel de microgestión me asusta un poco.
Andy Drucker
2
Esto se debe a que su respuesta no debe comenzar con "Hola Gil". No es un correo electrónico personal, es una publicación en un sitio web público. Por supuesto, los gustos de ustedes no son los objetivos de esto; son los usuarios nuevos los que desconocen estas convenciones que el software pretende controlar.
Yuval Filmus
1
Mi opinión es que está bien reconocer cuando uno está escribiendo en respuesta a la contribución de otra persona. Esto es normal y positivo en muchos entornos en línea. Traté de hacerlo de la manera más breve posible, por dirección personal; No veo nada malo en eso.
Andy Drucker
2
Buena construcción! Tengo una pregunta: que f sea la función indicadora de L ', y h sea como en la pregunta de Gil. Ahora, su argumento muestra que h está de acuerdo con f on y's que son palabras de código legales. Pero, ¿qué tal si no son palabras de código legales?
O Meir
2
¿Se puede implementar tal cosa con monótono ? f
Gil Kalai