P com oráculo de fatoração inteira

Acabei de ler a pergunta " A fatoração inteira é um problema NP-completo? " ... então decidi gastar parte da minha reputação :-) fazendo outra pergunta com P ( Q é trivial ) ≈ 1 :$Q$$P(\text{Q is trivial}) \approx 1$

Se é um oráculo que resolve inteiro fatoração, o que é o poder da P A ? $A$$P^A$

Eu acho que isso torna a criptografia de chave pública baseada em RSA insegura ... mas, além disso, existem outros resultados notáveis?

Não tenho uma resposta para sua pergunta, mas sei que uma noção semelhante foi estudada muito recentemente, sob o nome de "segurança baseada em anjo".

O primeiro artigo que estuda esse conceito é Prabhakaran & Sahai (STOC '04) . Em particular, eles escreveram no resumo:

[...] damos ao adversário acesso a algum poder computacional super-polinomial.

Outro artigo importante que discute essa noção é o de Canetti, Lin, & Pass (FOCS 2010) . Eu assisti algumas partes da apresentação da conferência (em techtalks ) e, se bem me lembro, elas começam com um exemplo semelhante ao que você mencionou na pergunta.

Obviamente, qualquer problema de decisão que possa ser reduzido a fatoração pode ser resolvido com um oráculo de fatoração. Mas como temos a capacidade de fazer várias consultas, tentei pensar em um problema não trivial para o qual alguém desejaria fazer várias consultas.

O problema de calcular a função totiente de Euler parece ser um problema. Não sei como resolver a versão de decisão desse problema com uma redução de Karp na versão de decisão do fatoramento. Mas com as reduções de Turing, é fácil reduzir isso ao fatoramento.

Elaborando sobre resposta anterior Joe: nota que . O último é o segundo mais baixo na classe "baixo" hierarquia : o que quer dizer que N P N P ∩ C O N P = N P . Isto implica, em particular, que P FATORAÇÃO ⊆ N P FATORAÇÃO ⊆ N P . Podemos fazer observações semelhantes para C S N P e B Q $\textrm{FACTORING} \in \mathsf{NP \cap coNP}$$\mathsf{NP^{NP \cap coNP} = NP}$

$P^A\subseteq \Delta_2^P$

$\mbox{FNP}$$P \subseteq P^A \subseteq \Delta_2^p$$P^{NP}$$\mbox{BQP}$$P \subseteq P^A \subseteq P^{NP \cap BQP}$