Barreras para separar otras clases de complejidad

9

¿ Las pruebas naturales , la relativización y la algebrización también afectan la separación de otras clases de complejidad como etc.?LNLNPcoNPPHPSPACE

Por ejemplo, la barrera de pruebas naturales debería afectar cualquier prueba de ya que separará . Sin embargo, la relación entre y no parece tener mucho con OWF en comparación con la relación entre y . Entonces, ¿las pruebas naturales afectan la separación más fuerte de ?P N P N P C o N P P N P N P C o N PNPCoNPPNPNPCoNPPNPNPCoNP

T ....
fuente
Sé que la línea superior del papel ( cs.umd.edu/~gasarch/BLOGPAPERS/natural.pdf ) tiene , P N P , P N C . Es por eso que excluí a P de la lista anterior. Como sé que N P C o N P spearates P y N P también incluí la pregunta por separado. Entonces, ¿tiene una cita donde dice específicamente N P C o N PPPSPACEPNPPNCPNPCoNPPNPNPCoNP?
T ....

Respuestas:

12

Hay (al menos) dos áreas donde las barreras existentes tienen poco que decir:

Límites inferiores de ACC No se conoce ninguna barrera para demostrar que TC0 no está en ACC (no uniforme), aparte de la posibilidad de que la separación sea falsa. No está claro si la barrera Natural Proofs debería aplicarse al ACC. La pregunta se reduce a: ¿deberíamos esperar que haya funciones pseudoaleatorias implementables en ACC?

LOGSPACE vs NP Como lo señala Fortnow , los mecanismos existentes de oráculo para el cálculo limitado por el espacio no parecen presentar una barrera real para LOGSPACE vs NP. Que yo sepa, los modelos de oráculo conocidos que producen un colapso de LOGSPACE y NP también colapsan ESPACIO DE LOGO ALTERNATIVO (es decir, P) y POLÍTICO ALTERNATIVO (es decir, PSPACE), por lo tanto, estos oráculos tratan modelos computacionales alternativos de manera inconsistente con la realidad (ya que LOGSPACE no es igual a a PSPACE).

Ryan Williams
fuente
6

El resultado de Razborov y Rudich en su papel de pruebas naturales es bastante general. No está restringido a vs. N P .PNP

Personalmente, me gusta la claridad de la explicación en el reciente libro de Stasys Jukna " Complejidad de la función booleana: avances y fronteras ":

Definición 18.30. Una función con l < n se denomina generador pseudoaleatorio seguro ( s , ϵ ) si para cualquier circuito C de tamaño s en n variables, | P r [ C ( y ) = 1 ] - P r [ C ( G (sol:{0 0,1}l{0 0,1}nortel<norte(s,ϵ)Csnorte donde y se elige uniformemente al azar en { 0 , 1 } n , yx en { 0 , 1 } l .

El |PAGSr[C(y)=1]-PAGSr[C(sol(X))=1]El |<ϵ,
y{0 0,1}norteX{0 0,1}l

Definición 18.31. Sea una función booleana. Decimos que f es ( s , ϵ ) -duro si para cualquier circuito C de tamaño s , | P r [ C ( x ) = f ( x ) ] - 1F:0 0,1norte0 0,1F(s,ϵ)Cs dondexse elige uniformemente al azar en{0,1}n.

El |PAGSr[C(X)=F(X)]-12El |<ϵ,
X{0 0,1}norte

Un generador de funciones pseudoaleatorio es una función booleana . Al establecer las variables y al azar, obtenemos su subfunción aleatoria f y ( x ) = f ( x , y ) . Deje h : { 0 , 1 } n{ 0 , 1F(X,y):{0 0,1}norte+norte2{0 0,1}yFy(X)=F(X,y) ser una función booleana verdaderamente aleatoria. Un generador f ( x , y ) es seguro contraataques Γ si para cada circuito C en Γ , | P r [ C ( f y ) = 1 ] - P r [ C ( h ) = 1 ] | < 2 - n 2 .h:{0 0,1}norte{0 0,1}F(X,y)ΓCΓ

El |PAGSr[C(Fy)=1]-PAGSr[C(h)=1]El |<2-norte2.

Una prueba natural contra Λ es una propiedad Φ : B n0 , 1 que satisface las siguientes tres condiciones: 1. La utilidad contra Λ : Φ ( f ) = 1 implica f Λ . 2. Amplitud: Φ ( f ) = 1 para al menos 2 - O ( n ) fracción de todas las funciones 2 2 n f ΓΛΦ:sinorte0 0,1
ΛΦ(F)=1FΛ
Φ(F)=12-O(norte)22norte . 3. Constructividad: Φ Γ , es decir, cuando se mira como una función booleana en N = 2 n variables, la propiedad Φ pertenece a la clase Γ . Fsinorte
ΦΓnorte=2norteΦΓ

Teorema 18.35. Si una clase de complejidad contiene un generador de funciones pseudo-aleatorio que es seguro contra la gamma-ataques, entonces no hay Γ prueba -natural contra Λ .ΛΓΛ

Las preguntas son: 1. ¿Creemos si hay funciones tan difíciles? 2. ¿Cuán constructivo / grande esperamos que sean las propiedades en las posibles pruebas de separación actuales?

En la otra dirección, Razbarov ha mencionado en varios lugares que él personalmente ve el resultado como una guía sobre qué evitar y no como un obstáculo esencial para probar los límites inferiores.

Además de los documentos de Ryan Williams durante los últimos años, hubo dos documentos que ha mencionado:

  1. nortePAGSPAGS

  2. norteC1TC0 0TC0 0

La relativización y la algebraización son un poco más complicadas y dependen de la forma en que definimos la relaztivización para estas clases. Pero como regla general, la diagonalización simple (una diagonalización que usa el mismo contraejemplo para todas las máquinas que computan la misma función, es decir, el contraejemplo solo depende de qué máquinas en el cómputo más pequeño y no depende de su código y cómo computan ) no puede separar estas clases.

Es posible extraer funciones de diagonalización no simple de resultados de diagonalización indirecta, como los límites inferiores del espacio de tiempo para SAT.

Kaveh
fuente
PAGSnortePAGSLnorteLnortePAGSConortePAGSPAGSHPAGSSpagsunaCmi
nortePAGSCoNPPHPSPACENPAGSConortePAGSL
1
Γ
@JAS, por cierto, si fuera usted, no aceptaría una respuesta tan rápido, podría obtener mejores respuestas.
Kaveh
oh ok ... No estoy seguro de qué mejor se puede dar aparte de lo que está en el libro.
T ....