Candidats naturels pour la hiérarchie au sein de NPI

Supposons que . est la classe de problèmes dans qui ne sont ni dans ni dans -hard. Vous pouvez trouver une liste des problèmes supposés être ici . $\mathsf{P} \neq \mathsf{NP}$ $\mathsf{NPI}$ $\mathsf{NP}$ $\mathsf{P}$ $\mathsf{NP}$ $\mathsf{NPI}$

Le théorème de Ladner nous dit que si $\mathsf{NP}\neq\mathsf{P}$ alors il y a une hiérarchie infinie de problèmes $\mathsf{NPI}$ , c'est-à-dire qu'il y a des problèmes $\mathsf{NPI}$ qui sont plus difficiles que d'autres $\mathsf{NPI}$ problèmes.

Je recherche des candidats pour de tels problèmes, c'est-à-dire que je suis intéressé par des paires de problèmes
- $A,B \in \mathsf{NP}$ ,
- $A$ et $B$ sont supposés être $\mathsf{NPI}$ ,
- $A$ est connu pour se réduire à $B$ ,
- mais il n'y a pas des réductions connues de $B$ à $A$ .

Encore mieux s'il existe des arguments pour les soutenir, par exemple, il y a des résultats que $B$ ne réduit pas à $A$ supposant certaines conjectures en théorie de la complexité ou en cryptographie.

Existe-t-il des exemples naturels de tels problèmes?

Exemple: Le problème d'isomorphisme graphique et le problème de factorisation d'entier sont supposés être dans $\mathsf{NPI}$ et il existe un argument soutenant ces conjectures. Y a-t-il des problèmes de décision plus difficiles que ces deux-là mais pas connus pour être $\mathsf{NP}$ -hard?

complexity-theory np-hard Mohammad Al-Turkistany
la source

Vous recherchez donc des problèmes tels que avec et ?

P \in N P

$P \in \mathrm{NP}$

P_{1} \leq_{p} P \leq_{p} P_{2}

$P_1 \leq_p P \leq_p P_2$

P_{1} \in N P I

$P_1 \in \mathrm{NPI}$

P_{2} \in N P C

$P_2 \in \mathrm{NPC}$

Raphael

Oui, mais il n'y a pas de réduction connue de P à P1 (de même aucune réduction connue de P2 à P).

Mohammad Al-Turkistany

il y a plusieurs problèmes avec un statut similaire à l'affacturage, voir cet article par Papadimitriou theory.stanford.edu/~megiddo/pdf/papadimX.pdf

Marcos Villagra

d'ailleurs, nous avons une très belle liste dans cstheory cstheory.stackexchange.com/questions/79/…

Marcos Villagra

pourquoi la liste à laquelle Marcos renvoie n'est-elle pas la réponse à votre question?

Suresh

Réponses:

J'ai trouvé un joli problème appelé ModularFactorial . Prendre en entrée deux entiers à chiffres et , et la sortie . Ce problème est au moins aussi difficile que l' affacturage et ne sait pas qu'il est difficile pour FNP . La référence est le livre récent (et magnifique) de Cristopher Moore et Stephan Mertens The Nature of Computation , page 79. $n$ $x$ $y$ $x! \mod y$

Marcos Villagra
la source

Je crois que le PO recherche des problèmes dans NP. Pouvez-vous reformuler cela comme un problème de décision?

Zach Langley

FNP est la version de fonction (c'est-à-dire les problèmes de recherche) de NP. En fait, l'affacturage n'est pas en NP, c'est FNP. Par exemple, le problème de décision pour l'affacturage est trivial, la complexité est juste O (1), mais le problème de recherche est la partie difficile. Étant donné que le PO a donné l'exemple de l'affacturage, je pense que c'est également une réponse valable.

Marcos Villagra

L'affacturage peut être reformulé en un problème de décision comme suit: étant donné un entier et un entier , contient-il un facteur avec ? Existe-t-il une version décisionnelle analogue du problème ModularFactorial?

n

$n$

k

$k$

n

$n$

d

$d$

1 < d \leq k

$1 < d \le k$

Zach Langley

@Marcos, merci. Je m'intéresse aux problèmes de décision en NP.

Mohammad Al-Turkistany

@ZachLangley, oui bien sûr, je suis d'accord, mais je pensais dans une autre version de décision, à savoir, "est-ce que x a un facteur?". La réponse est simplement «oui» toujours. Vous pouvez faire de même avec modularfactorial, donner un entier k et décider si est supérieur ou non à .

x! \mod y

$x!\mod y$

k

$k$

Marcos Villagra