¿ Las pruebas naturales , la relativización y la algebrización también afectan la separación de otras clases de complejidad como etc.?
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 P
cc.complexity-theory
barriers
T ....
fuente
fuente
Respuestas:
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).
fuente
El resultado de Razborov y Rudich en su papel de pruebas naturales es bastante general. No está restringido a vs. N P .PAGS N P
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 ":
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:
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.
fuente