Les réductions de plusieurs et les réductions de Turing définissent-elles le même PNJ de classe

11

Je me demande si les classes NPC définies par plusieurs réductions et les réductions de Turing sont égales.

Edit: Une autre question, est-ce que les réductions de Turing ne font que réduire les classes C et co-C pour certains C ou existe-t-il une classe telle qu'il existe un problème qui n'est pas dans sous la réduction de Karp et qui est en sous la réduction de Turing ?C ∪ c o - C CCC∪co-CC

cc.complexity-theory np-hardness reductions Ludovic Patey
la source
4
Avez-vous lu en.wikipedia.org/wiki/… ?
Jukka Suomela
Merci pour votre lien. Il répond à la première partie de ma question, mais ne répond pas à la question de savoir s'il y a des problèmes qui ne se posent pas en co-C sous la réduction de plusieurs et qui sont en C sous la réduction de Turing, pour tout C.
Ludovic Patey
1
Désolé, cela peut sembler une question élémentaire ou peut-être que je ne pense pas directement à cette heure tardive mais il me manque quelque chose dans l'article wiki. L'article dit que sous les réductions Cook, NP-complete est égal à co-NP-complete, mais je ne le vois pas. NP-hard est égal à co-NP-hard wrt Cook réductions, mais NP-complete signifie être à la fois NP-hard ET NP , et je ne vois pas pourquoi (par exemple) TAUT serait en NP? C'est-à-dire que TAUT est co-NP-dur sous les réductions Cook, mais cela ne suffit pas pour être NP-complet.
Kaveh
@Monoid, vous devriez reformuler votre question pour refléter cette clarification. En tant que telle, la question est ambiguë
Suresh Venkat
doublon possible des réductions de plusieurs par rapport aux réductions de Turing pour définir le PNJ
Suresh Venkat

Réponses:

7

Jetez un œil à cette question et surtout à cette réponse d'Aaron Sterling. En bref: "ils sont supposés être des notions distinctes."

Matthias
la source
Je sais que si NP! = Co-NP, ce sont des notions distinctes parce que la réduction de Turing les effondre, mais pourrait-il y avoir des différences qui ne seraient pas des effondrements, par exemple un problème dans NPI sous plusieurs réductions et dans NPC sous réduction de Turing ?
Ludovic Patey
@ Monoïd: NP ≠ coNP n'implique pas (au moins de façon évidente) que les deux notions de réductions soient distinctes. Je crains que vous ne confondiez la classe NP (qui est définie indépendamment du choix de la notion de réductions) avec la classe des problèmes de décision réductibles à NP (qui dépend du choix de la notion de réductions).
Tsuyoshi Ito
Oups, mon commentaire précédent était faux. Si NP ≠ coNP, les deux notions de réduction sont évidemment distinctes (SAT est inconditionnellement réductible à UNSAT, mais SAT est plusieurs réductible à UNSAT si et seulement si NP = coNP).
Tsuyoshi Ito du
10

La BP "Hiérarchie booléenne" est toute une hiérarchie de combinaisons de problèmes NP sous des réductions de Karp qui sont toutes dans P ^ NP.

Noam
la source
9

Pour autant que je sache, cette question comprend en réalité deux questions distinctes, la première apparaissant dans le titre et la seconde après le montage.

(1) Les réductions de plusieurs et les réductions de Turing définissent-elles le même ensemble de problèmes NP-complets (c.-à-d. Problèmes qui sont à la fois dans NP et à qui SAT peut être réduit)? La question de savoir si le NPC dans le cadre des réductions de Turing est le même que le NPC dans le cadre de plusieurs réductions était encore un problème ouvert il y a sept ans, et je ne pense pas qu'il ait été fermé depuis. Voir cette enquête du bulletin ACM SIGACT News de juin 2003 pour plus de détails.

(2) À quelle classe de problèmes SAT a-t-il une réduction de Turing, et vice versa? C'est la classe des problèmes NP-difficiles (sous les réductions de Turing) qui sont dans P NP . Pour plus d'informations à ce sujet, voir la réponse de Noam.

Peter Shor
la source
le lien ne fonctionne pas.
T ....
8

Cela ne répond pas à votre question, mais on pourrait poser la même question pour des réductions plus faibles. Par exemple, l'ensemble des problèmes NP-complets change-t-il si nous autorisons uniquement les réductions d'espace logarithmique, ou uniquement les réductions AC 0 , ou même les réductions NC 0 . Un fait surprenant est que tous les problèmes NP-complets connus sont complets même avec des réductions NC 0 .

Référence: Agrawal, M., Allender, E. et Rudich, S. 1997 Reductions in Circuit Complexity: an Isomorphism Theorem and a Gap Theorem.

Robin Kothari
la source
Cette question concernant des réductions plus faibles est-elle toujours ouverte? Si j'ai un problème qui était NP complet sous les réductions P / poly ou BPP, mais apparemment pas sous les réductions P sans supposer des hypothèses théoriques de nombre non prouvées, cela vaut-il la peine de le noter?
Peter Shor
@Peter: Dans l'article que j'ai cité, il reste ouvert s'il y a un problème qui est NP-complet sous des réductions de temps polynomiales qui n'est pas NP-complet sous des réductions AC ^ 0. Cette question a reçu une réponse en réduisant la complexité des réductions . Ils montrent un problème NP-complet avec des réductions ACC mais pas des réductions AC ^ 0. Aucun de ces articles ne semble commenter les problèmes qui sont NP-complet sous des réductions plus fortes que le temps polynomial, et comment cela se rapporte à la possibilité d'être NP-complet sous des réductions de polytime.
Robin Kothari
1

Cet article prétend montrer que l'existence d'un problème TF N EEXP qui est
[suffisamment difficile à résoudre avec zéro erreur dans le pire des cas] implique l'existence d'
un "langage complet de Turing pour NP qui n'est pas une table de vérité complète pour NP. "

D'un autre côté, je n'ai essayé de lire aucune de leurs preuves revendiquées pour ce résultat,
mais la proposition 2 et / ou ses preuves démontrent une mauvaise compréhension de la définition de ZPP :
il semble qu'ils aient réellement besoin de " FP peut résoudre tout F ZPP ", plutôt que" ZPP = P ".


la source