P avec oracle de factorisation entière

18

Je viens de lire la question " La factorisation des nombres entiers est-elle un problème NP-complet? " ... alors j'ai décidé de dépenser une partie de ma réputation :-) en posant une autre question ayant : $Q$ $P(\text{Q is trivial}) \approx 1$

Si est un oracle qui résout la factorisation entière, quelle est la puissance de ? $A$ $P^A$

Je pense que cela rend la cryptographie à clé publique basée sur RSA précaire ... mais à part cela, y a-t-il d'autres résultats remarquables?

cc.complexity-theory oracles factoring Marzio De Biasi
la source

3

@Pour cette partie, P(Q is trivial)=1c'est une blague, non?

Pratik Deoghare

Cette question suggère une question connexe et (peut-être) plus naturelle: si R est un oracle qui renvoie f _ (_ M , n ) comme le temps d'exécution maximal d'une machine de Turing à temps polynomial M sur toutes les entrées de longueur n , quelle est la puissance de P ^ R?

John Sidles

2

@Vor: N'est-ce pas la même chose que de demander "Quels sont les problèmes que le temps de Turing polynomial peut réduire à une factorisation entière?" Ou aviez-vous l'intention de demander autre chose?

Joshua Grochow

Je suis un débutant, donc ma question est presque une curiosité. Tout est parti d'une pensée simple: dehors "dans le monde réel" je vois de nombreux problèmes NP-complets (un facteur essayant de réserver ses forces, une famille qui déménage et qui veut monter ses meubles dans un camion, ...: - ))). Mais je ne vois pas de "problèmes d'affacturage" ... bien qu'ils PEUVENT être plus simples (entre P et NPC). ... peut-être que la réalité déteste les multiplications :-D :-D

Marzio De Biasi

1

Voir aussi Conséquences de l'affacturage étant en P?

Jukka Suomela

11

Je n'ai pas de réponse à votre question, mais je sais qu'une notion similaire a très récemment été étudiée, sous le nom de «sécurité basée sur les anges».

Le premier article étudiant ce concept est Prabhakaran & Sahai (STOC '04) . En particulier, ils ont écrit dans l'abstrait:

[... nous donnons à] l'adversaire accès à une puissance de calcul super-polynomiale.

Un autre article important qui traite de cette notion est celui de Canetti, Lin et Pass (FOCS 2010) . J'ai regardé certaines parties de leur présentation de conférence (sur techtalks ), et si je me souviens bien, ils commencent par un exemple similaire à ce que vous avez mentionné dans la question.

MS Dousti
la source

13

Évidemment, tout problème de décision qui peut être réduit à l'affacturage peut être résolu avec un oracle d'affacturage. Mais comme nous avons la possibilité de faire plusieurs requêtes, j'ai essayé de penser à un problème non trivial pour lequel on voudrait faire plusieurs requêtes.

Le problème du calcul de la fonction de totient d'Euler semble être un tel problème. Je ne sais pas comment résoudre la version décisionnelle de ce problème par une réduction de Karp à la version décisionnelle de l'affacturage. Mais avec les réductions Turing, il est facile de réduire cela à l'affacturage.

Robin Kothari
la source

3

Voici un article connexe dans MO concernant la complexité de la fonction de calcul de totient.

Hsien-Chih Chang 張顯之

Petit ajout: il y a aussi des réductions de temps polynomiales dans l'autre sens, calculant la fonction Totient d'Euler -> Factoring. Je n'ai pas vérifié si les réductions connues fonctionnent pour la version de décision de ces problèmes. Pourtant, être capable de calculer la fonction Totient (ou même un multiple fixe) vous donne la possibilité de factoriser. Le livre de Shoup y consacre un chapitre.

Juan Bermejo Vega

9

Développant réponse précédente Joe: A noter que . Cette dernière est la deuxième classe la plus basse dans la hiérarchie de « faible » : ce qui revient à dire que . Cela implique en particulier que Nous pouvons faire des remarques similaires pour et $\textrm{FACTORING} \in \mathsf{NP \cap coNP}$ $\mathsf{NP^{NP \cap coNP} = NP}$

P^{AFFACTURAGE} \subseteq N P^{AFFACTURAGE} \subseteq N P .

$\mathsf{P^{\textrm{FACTORING}} \subseteq NP^{\textrm{FACTORING}}} \subseteq \mathsf{NP}.$

c o N P

$\mathsf{coNP}$

B Q P

$\mathsf{BQP}$ , Pour montrer ce qu ' au moins à un niveau à grains grossiers,

a les mêmes limites que la complexité du problème

lui-même, qui est - à - dire

P^{FACTORING}

$\mathsf P^{\textrm{FACTORING}}$

FACTORING

$\textrm{FACTORING}$

P^{AFFACTURAGE} \subseteq N P \cap c o N P \cap B Q P .

$\mathsf{P^{\textrm{FACTORING}} \subseteq NP \cap coNP \cap BQP}.$

Niel de Beaudrap
la source

N P \cap c o N P

$NP \cap coNP$

3

U P \cap c o U P

$\mathsf{UP} \cap \mathsf{coUP}$

6

$P^A\subseteq \Delta_2^P$

Marcus Ritt
la source

5

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

Joe Fitzsimons
la source

P avec oracle de factorisation entière

Réponses: