Contenções conjuntas mais conhecidas para / por NP e Parity-P?

18

Paridade-P é o conjunto de idiomas reconhecidos por uma máquina de Turing não determinística que só pode distinguir entre um número par ou um número ímpar de caminhos de "aceitação" (em vez de um número zero ou diferente de zero de caminhos de aceitação). Assim Paridade-P é basicamente PP atrofiado irmão mais novo de: enquanto que as contagens de PP se ou não o número de percursos de aceitação de um NP-máquina é ou não a maioria ( ou seja, o bit mais significativo do que a quantidade), Paridade-P indica o bit menos significativo do número de caminhos aceitos.

Como NP, Parity-P contém UP (que contém P, "provavelmente" estritamente); e, como NP, a Paridade-P está contida no PSPACE.

Questão. Quais são os limites superior e inferior da articulação mais conhecidos para NP e Parity-P?

cc.complexity-theory complexity-classes np Niel de Beaudrap
fonte

Respostas:

17

Por Valiant-Vazirani, NP está contido no ponto BP Parity-P (que obviamente contém Parity-P). Além disso, Toda mostrou que o PH está no ponto BP Parity-P, que está em P ^ (# P) (que está no PSPACE).

Para limites inferiores, acho que ambas as classes contêm uma classe conhecida como FewP, que contém UP e é como NP, mas você pergunta que as strings na linguagem têm no máximo polinomialmente muitos caminhos aceitáveis.

[Atualização: erro de digitação corrigido BPP em vez de BP]

Manu
fonte
5
Um corolário da contenção PH no ponto BPP, Paridade-P, é que a Paridade-P não está contida na Hierarquia Poli, a menos que a Hierarquia entre em colapso.
Andy Drucker
4
Isso ocorre porque, se Paridade-P estiver em Sigma_k-P, PH estará no ponto BPP Sigma_k-P, que está contido em Pi_ (k + 1) -P. (esta última contenção resulta de uma 'operador' generalização directa do resultado que o BPP está em Sigma_2 P cruzam Pi_2 P.)
Andy Drucker
4
Eu acho que é plausível que a Paridade-P do ponto BPP esteja contida em P ^ (Paridade-P). Se isso é verdade, então PH está contido em P ^ (Paridade), que está contido em (Paridade-P) ^ (Paridade-P), que na verdade é igual à Paridade-P. O que não tenho certeza é se algum artigo sobre dureza versus aleatoriedade fornece uma hipótese que implica o ponto BPP Paridade-P contido em P ^ (Paridade-P).
Andy Drucker
4
Finalmente, a Paridade-P se distingue de NP e outras classes de PH, pois é conhecida por ter reduções de pior caso para caso médio. Ou seja, se a Paridade-P não estiver em P, ela conterá problemas de distribuição que são comuns em casos médios. Veja Feigenbaum-Fortnow, "Auto-redutibilidade aleatória de conjuntos completos".
Andy Drucker
3
Aqui está a idéia geral: seja C uma classe de complexidade. Um idioma L está em (BPP ponto C) se existe um idioma S em C, consistindo em pares codificados (x, r), de modo que: -if x esteja em L, então para 2/3 de todo r, o par (x, r) está em S; -se x não estiver em L, então, para 2/3 de todo r, o par (x, r) não estará em S. (Tecnicamente, o comprimento de r depende de x e é necessário que haja no máximo algum polinômio em | x |.)
Andy Drucker