Les confinements articulaires les plus connus pour / par NP et Parity-P?

18

La parité-P est l'ensemble des langages reconnus par une machine de Turing non déterministe qui ne peut distinguer qu'un nombre pair ou un nombre impair de chemins "d'acceptation" (plutôt qu'un nombre nul ou non nul de chemins d'acceptation). Ainsi la parité-P est essentiellement PP jeune frère rabougris de: en PP compte si oui ou non le nombre d'accepter les chemins d'une machine NP est une majorité ou non ( à savoir le bit le plus significatif de cette quantité), la parité-P indique le bit le moins significatif du nombre de chemins d'acceptation.

Comme NP, Parity-P contient UP (qui contient P, "probablement" strictement ainsi); et comme NP, Parity-P est contenu dans PSPACE.

Question. Quelles sont les limites supérieures et inférieures communes les mieux connues pour NP et Parity-P?

cc.complexity-theory complexity-classes np Niel de Beaudrap
la source

Réponses:

17

Par Valiant-Vazirani, NP est contenu dans BP dot Parity-P (qui contient évidemment Parity-P). De plus, Toda a montré que PH est en BP dot Parity-P qui est en P ^ (# P) (qui est en PSPACE).

Pour les bornes inférieures, je pense que les deux classes contiennent une classe connue sous le nom de FewP qui contient UP et est comme NP, mais vous demandez que les chaînes du langage aient au plus polynomialement beaucoup de chemins d'acceptation.

[Mise à jour: correction de la faute de frappe BPP au lieu de BP]

Manu
la source
5
Un corollaire du PH de confinement dans le point BPP Parity-P, est que Parity-P n'est pas contenu dans la Poly Hiérarchie à moins que cette Hiérarchie ne s'effondre.
Andy Drucker
4
Cela suit parce que, si Parity-P est dans Sigma_k-P, alors PH est dans le point BPP Sigma_k-P, qui est contenu dans Pi_ (k + 1) -P. (ce dernier confinement découle d'une simple généralisation par l'opérateur du résultat que BPP est dans Sigma_2 P intersecte Pi_2 P.)
Andy Drucker
4
Je pense qu'il est plausible que le point BPP Parity-P soit contenu dans P ^ (Parity-P). Si cela est vrai, alors PH est contenu dans P ^ (Parité), qui est contenu dans (Parité-P) ^ (Parité-P), qui est en fait égal à Parité-P. Ce dont je ne suis pas sûr, c'est de savoir si des articles sur la dureté par rapport au hasard donnent une hypothèse qui implique le point BPP Parity-P contenu dans P ^ (Parity-P).
Andy Drucker
4
Enfin, Parity-P se distingue du NP et des autres classes de PH en ce qu'il est connu pour avoir des réductions du pire cas au cas moyen. Autrement dit, si Parity-P n'est pas dans P, alors il contient des problèmes de distribution qui sont durs dans le cas moyen. Voir Feigenbaum-Fortnow, "Auto-réductibilité aléatoire d'ensembles complets".
Andy Drucker
3
Voici l'idée générale: soit C une classe de complexité. Un langage L est en (point BPP C) s'il existe un langage S en C, constitué de paires codées (x, r), telles que: -si x est en L, alors pour 2/3 de tout r, la paire (x, r) est dans S; -si x n'est pas dans L, alors pour 2/3 de tous r, la paire (x, r) n'est pas dans S. (Techniquement, la longueur de r dépend de x et doit être au plus un polynôme dans | x |.)
Andy Drucker