Obstacles à la séparation d'autres classes de complexité

9

Do Natural preuves , relativisation et algébrisation affectent également la séparation des autres classes de complexité comme etc?LNLNPcoNPPHPSPACE

Par exemple barrière des preuves naturelles doit affecter toute preuve de puisqu'elle séparera P N P . Cependant relation entre N P et C o N P ne semble pas avoir beaucoup avec owfs par rapport à la relation entre P et N P . Les preuves naturelles affectent-elles donc la séparation plus forte de N P C o N P ?NPCoNPPNPNPCoNPPNPNPCoNP

T ....
la source
Je sais que la ligne supérieure du papier ( cs.umd.edu/~gasarch/BLOGPAPERS/natural.pdf ) a , P N P , P N C . C'est pourquoi j'ai exclu P de la liste ci-dessus. Puisque je sais que N P C o N P spearates P et N P, j'ai également inclus la question séparément. Alors avez-vous une citation où il est dit spécifiquement N P C o N PPPSPUNECEPNPPNCPNPCoNPPNPNPCoNP?
T ....

Réponses:

12

Il y a (au moins) deux domaines où les obstacles existants ont peu à dire:

Limites inférieures de l'ACC Il n'y a pas d'obstacle connu pour prouver que TC0 n'est pas dans l'ACC (non uniforme) - autre que la possibilité que la séparation soit fausse. Il n'est pas clair si la barrière Natural Proofs devrait s'appliquer à l'ACC. La question se résume à: devons-nous nous attendre à ce qu'il y ait des fonctions pseudo-aléatoires implémentables dans ACC?

LOGSPACE vs NP Comme l'a souligné Fortnow , les mécanismes oracle existants pour le calcul limité dans l'espace ne semblent pas présenter un véritable obstacle à LOGSPACE vs NP. À ma connaissance, les modèles d'oracle connus qui produisent un effondrement de LOGSPACE et NP s'effondrent également ALTERNATING LOGSPACE (c.-à-d. P) et ALTERNATING POLYTIME (c.-à-d. PSPACE). à PSPACE).

Ryan Williams
la source
6

Le résultat de Razborov et Rudich dans leur papier de preuves naturelles est assez général. Il ne se limite pas à par rapport à N P .PNP

Personnellement , j'aime la clarté de l'explication contenue dans le livre récent de Stasys Jukna " Complexité de la fonction booléenne: avancées et frontières ":

Définition 18.30. Une fonction avec l < n est appelée générateur pseudo-aléatoire sécurisé ( s , ϵ ) si pour tout circuit C de taille s sur n variables, | P r [ C ( y ) = 1 ] - P r [ C ( G (g:{0,1}l{0,1}nl<n(s,ϵ)Csn y est choisi uniformément au hasard dans { 0 , 1 } n , et x dans { 0 , 1 } l .

|Pr[C(y)=1]-Pr[C(g(X))=1]|<ϵ,
y{0,1}nX{0,1}l

Définition 18.31. Soit une fonction booléenne. On dit que f est ( s , ϵ ) -difficile si pour tout circuit C de taille s , | P r [ C ( x ) = f ( x ) ] - 1F:0,1n0,1F(s,ϵ)Csxest choisi uniformément au hasard dans{0,1}n.

|Pr[C(X)=F(X)]-12|<ϵ,
X{0,1}n

Un générateur de fonction pseudo-aléatoire est une fonction booléenne . En fixant les variables y au hasard, nous obtenons sa sous-fonction aléatoire f y ( x ) = f ( x , y ) . Soit h : { 0 , 1 } n{ 0 , 1F(X,y):{0,1}n+n2{0,1}yFy(X)=F(X,y) être une fonction booléenne vraiment aléatoire. Un générateur f ( x , y ) est protégé contre lesattaques Γ si pour chaque circuit C dans Γ , | P r [ C ( f y ) = 1 ] - P r [ C ( h ) = 1 ] | < 2 - n 2 .h:{0,1}n{0,1}F(X,y)ΓCΓ

|Pr[C(Fy)=1]-Pr[C(h)=1]|<2-n2.

Une preuve -naturelle contre Λ est une propriété Φ : B n0 , 1 satisfaisant aux trois conditions suivantes: 1. Utilité contre Λ : Φ ( f ) = 1 implique f Λ . 2. Grandeur: Φ ( f ) = 1 pour au moins 2 - fraction O ( n ) de toutes les 2 2 n fonctions f ΓΛΦ:Bn0,1
ΛΦ(F)=1FΛ
Φ(F)=12-O(n)22n . 3. Constructivité: Φ Γ , c'est-à-dire que lorsqu'elle est considérée comme une fonction booléenne dans N = 2 n variables, la propriété Φ elle-même appartient à la classe Γ . FBn
ΦΓN=2nΦΓ

Théorème 18.35. Si une classe de complexité contient un générateur de fonction pseudo-aléatoire protégé contre les attaques Γ, il n'y a pas de preuve naturelle contre Γ contre Λ .ΛΓΛ

La question est: 1. Croyons-nous s'il existe de telles fonctions difficiles? 2. Dans quelle mesure pouvons-nous nous attendre à ce que les propriétés des preuves de séparation actuellement possibles soient constructives / importantes?

Dans l'autre sens, Razbarov a mentionné à divers endroits qu'il considère personnellement le résultat comme un guide à éviter et non comme un obstacle essentiel à la démonstration des limites inférieures.

Outre les articles de Ryan Williams au cours des dernières années, il a mentionné deux articles:

  1. NPP

  2. NC1TC0TC0

La relativisation et l'algèbre sont un peu plus délicates et dépendent de la façon dont nous définissons la relazivisation pour ces classes. Mais en règle générale, la diagonalisation simple (une diagonalisation qui utilise le même contre-exemple pour toutes les machines calculant la même fonction, c'est-à-dire que le contre-exemple ne dépend que des machines dans le plus petit calcul et ne dépend pas de leur code et de la façon dont elles calculent ) ne peut pas séparer ces classes.

Il est possible d'extraire des fonctions de diagonalisation non simples des résultats de diagonalisation indirecte comme les bornes inférieures de l'espace-temps pour SAT.

Kaveh
la source
PNPLNLNPcoNPPHPSpunece
NPCoNPPHPSPUNECENPCoNPL
1
Γ
@JAS, btw, si j'étais vous, je n'accepterais pas une réponse aussi rapidement, vous pourriez obtenir de meilleures réponses.
Kaveh
oh ok .... Je ne sais pas quoi de mieux que ce qui est dans le livre.
T ....