Consequências de

Eu tenho parte de uma tentativa de prova de . A tentativa prova consiste numa redução do Karp problema -completo cobertura de vértices 3-regular para sab. $\oplus \mathbf{P} \subseteq \mathbf{NP}$ $\oplus \mathbf{P}$ $\oplus$

Dado um gráfico cúbico , a redução gera uma fórmula CNF com as duas propriedades a seguir: $G$ $F$

$F$ tem no máximo tarefa satisfatória. $1$
$F$ é satisfatório se e somente se o número de coberturas de vértices de for ímpar. $G$

Questões

Quais seriam as consequências de ? Uma conseqüência que eu já estou ciente é a seguinte: seria redutível para por meio de redução aleatória nos dois lados. Em outras palavras, teríamos (usando o Teorema de Toda, que afirma que , substituindo apenas por ). Não sei se $\oplus \mathbf{P} \subseteq \mathbf{NP}$ $\mathbf{PH}$ $\mathbf{NP}$ $\mathbf{PH}\subseteq\mathbf{BPP}^{\mathbf{NP}}$ $\mathbf{PH}\subseteq\mathbf{BPP}^{\oplus\mathbf{P}}$ $\oplus\mathbf{P}$ $\mathbf{NP}$ $\mathbf{BPP}^{\mathbf{NP}}$ foi demonstrado está contido em algum nível $i$ da Hierarquia Polinomial: se sim, uma outra conseqüência seria que $\mathbf{PH}$ cai para esse nível $i$ . Além disso, sob as premissas de des aleatorização amplamente aceitas ( $\mathbf{BPP} = \mathbf{P}$ ), a Hierarquia Polinomial entraria em colapso entre o primeiro e o segundo nível, pois teríamos(me disseram que isso não é verdade, no entanto, não apagarei esta linha até entender completamente o porquê). $\mathbf{PH} = \mathbf{P}^\mathbf{NP} = \Delta_2^\mathbf{P}$

Se não me engano, a redução acima mencionada seria realmente mais do que . Isso provaria . Quais seriam as consequências de , além daquelas já implícitas por ? Não sei exatamente se traria mais surpresa às conseqüências já surpreendentes de , nem em que extensão. Intuitivamente, presumo que sim, e em grande parte. $\oplus \mathbf{P} \subseteq \mathbf{NP}$ $\oplus \mathbf{P} \subseteq \mathbf{UP}$ $\oplus \mathbf{P} \subseteq \mathbf{UP}$ $\oplus \mathbf{P} \subseteq \mathbf{NP}$ $\oplus \mathbf{P} \subseteq \mathbf{UP}$ $\oplus \mathbf{P} \subseteq \mathbf{NP}$

cc.complexity-theory graph-theory complexity-classes sat counting-complexity Giorgio Camerani
fonte

é fechada sob complemento, e a redução randomizado de PH para

é muitas-ona, daqui

realmente implica

, e

\oplus P

$\oplus\mathrm P$

\oplus P

$\oplus\mathrm P$

\oplus P \subseteq N P

$\oplus\mathrm P\subseteq\mathrm{NP}$

P H = Σ_{2}^{P} = Π_{2}^{P} = A M \cap c o A M

$\mathrm{PH}=\Sigma^P_2=\Pi^P_2=\mathrm{AM}\cap\mathrm{coAM}$

P H \subseteq N P / p o l y \cap c o N P / p o l y

$\mathrm{PH}\subseteq\mathrm{NP/poly}\cap\mathrm{coNP/poly}$ . O UP não faz muita diferença (veja a falta de algo útil em cstheory.stackexchange.com/questions/3887 ).

Emil Jeřábek

@ EmilJeřábek Obrigado pelo seu comentário interessante, eu não sabia disso. Eu sabia que a pergunta que você apontou-me, no entanto, eu teria esperado

(assim como

) a ser surpreendente, pelo menos, porque

não é conhecido por ter problemas completos. É interessante como não se sabe que algo amplamente conjecturado como falso (

) tenha, se for verdade, qualquer consequência chocante. Você pode considerar expandir o seu comentário em uma resposta ...

\oplus P \subseteq U P

$\oplus \mathbf{P}\subseteq\mathbf{UP}$

N P \subseteq U P

$\mathbf{NP}\subseteq\mathbf{UP}$

U P

$\mathbf{UP}$

N P \subseteq U P

$\mathbf{NP}\subseteq\mathbf{UP}$

Giorgio camerani

Não, você está completamente errado. BPP = P diz apenas que todo idioma computável por uma máquina BPP também é computável por uma máquina P. Não diz absolutamente nada sobre idiomas que são computáveis por uma máquina BPP com um oráculo não trivial. Por seu argumento defeituoso, NP = P implica

para cada

, que sabemos ser falso, portanto,

é resolvido. E, a esse respeito, seu argumento implicaria

, pois existem oráculos

para os quais

{N P}^{A} = P^{A}

$\mathrm{NP}^A=\mathrm P^A$

A

$A$

N P \neq P

$\mathrm{NP}\ne\mathrm P$

B P P \neq P

$\mathrm{BPP}\ne\mathrm P$

A

$A$

{B P P}^{A} \neq P^{A}

$\mathrm{BPP}^A\ne\mathrm P^A$ .

Emil Jeřábek

@Giorgio: Ele está apenas alegando que a linha de raciocínio que você considerou não funciona nessa circunstância. Parte relevante: "Se a máquina à qual eu anexo o oráculo é pelo menos tão poderosa, por que a inclusão não deveria acontecer?". Ele não parece dizer que a afirmação em si é falsa; apenas que sua intuição específica não funciona. Ainda não podemos descartar que aspectos probabilísticos do PPTM não poderiam se beneficiar mais desse oráculo. A TM probabilística tem mais ferramentas à sua disposição, mas a ferramenta pode não fornecer benefícios estritos sem outras (como o oracle NP).

Mdxn #

Mesmo com a suposição de que um PRNG forte o suficiente para reduzir P e BPP existe, não vejo por que isso necessariamente implica BPP com um oráculo NP e P com um oráculo NP deve ser o mesmo. Normalmente, os PRNGs têm a garantia de que nenhum circuito polisize pode distinguir sua saída de bits verdadeiramente aleatórios. Mas para as máquinas oracle, você precisa da garantia para todos os circuitos de polisize com portas NP permitidas, e isso é mais forte. Impagliazzo-Wigderson faz relativizar, mas você precisa para fortalecer a suposição de dureza ( eccc.hpi-web.de/report/1998/055/comment/1/download )

Sasho Nikolov

Consequências de

Respostas: