Y at-il des problèmes complets pour P et NP sous d'autres types de réductions?

Question

Je sais que la classe de complexité $ \ mathsf {P} $ a des problèmes complet w.r.t. $ \ Mathsf {NC} $ et $ \ mathsf {L} $ réductions.

sont ces deux classes les seules classes possibles de réductions dans lesquelles $ \ mathsf {P} $ a des problèmes complets?

En outre, quelles classes de réduction peut être utilisée pour $ \ mathsf {NP} $ à côté de la réduction du temps polynomiale?

Answer 1

Vos questions contiennent quelques phrases incorrectes ou peu claires. Ni « classe de complexité X a la réduction Y », ni « nous pouvons utiliser la réduction Y pour la classe de complexité X » est logique. En outre, il existe au moins deux définitions connues sous le nom de « la réduction du temps polynomiale, » qui sont tous deux utilisés pour étudier NP-complet: temps polynomiale aux multiples réductions et un polynôme temps des réductions de Turing. Mais dans cette réponse, je vais ignorer la différence entre de nombreuses réductions et-une réduction de Turing, et je vais me concentrer uniquement sur les restrictions de ressources de réductions, car sinon la réponse deviendra trop long et non ciblés.

Maintenant, je vais répéter ce que vous voudrez peut-être demander, et d'y répondre.

Y a-t-il des définitions de réductions par rapport auxquelles NP-complet peut être défini, autres que la réduction du temps polynomiale? Y a-t-il des définitions de réductions par rapport auxquelles P-complet peut être défini, autres que des réductions NC et log-space réductions?

Artem et Raphaël, vous pouvez définir ce que vous aimez.

Y at-il des définitions de réductions effectivement utilisées pour étudier NP-complet dans la littérature, autres que la réduction du temps polynomiale? Existe-t-il des définitions de réductions effectivement utilisées pour P-complet de l'étude dans la littérature, autres que des réductions et des réductions log-space NC?

Oui. Par exemple, Papadimitriou utilise des réductions log-espace tout au long de son manuel [Pap94], y compris la définition de NP-complet. (Note:. Dans [Pap94], le terme « L-réduction » signifie quelque chose de complètement différent de réduction log-espace) En ce qui concerne P-complétude, NC ^k réductions sont mentionné dans [GHMRSS00]. Ceci est un cas particulier de réductions NC, et plus générale que les réductions log-espace pour k =2.

Mais sont-ils vraiment des notions différentes, ou tout simplement des définitions différentes pour la même notion?

À l'heure actuelle, personne ne sait. Par exemple, réductibilité log-espace et réductibilité polynomial sont équivalentes si et seulement si L = P.

[GHMRSS00] Raymond Greenlaw, H. James Hoover, Satoru Miyano, Walter L. Ruzzo, Shuji Shiraishi et Takayoshi Shoudai. Le projet parallèle de calcul: Volumes I-III , 2000. http: // www. cs.armstrong.edu/greenlaw/research/PARALLEL/

[Pap94] Christos H. Papadimitriou. Complexité . Addison-Wesley, 1994.

Answer 2

Notez que si la classe de complexité $ C $ a un problème complet sous une classe de réductions $ A $, le même problème sera complet pour $ C $ sous et classe de réductions contenant $ A $.

En règle générale les preuves complétude passent par la classe beaucoup plus faible de réductions que d'habitude indiqué (par exemple sous $ \ mathsf {AC ^ 0} $ réductions). Toute classe de réductions contenant $ \ mathsf {AC ^ 0} $ SUFFIRAIT et il y a beaucoup de ces classes indénombrables.

Vous pouvez également consulter le document suivant:

• Agrawal, M, Allender, E., Impagliazzo, R., Pitassi, T., et Rudich, S., " Réduire la complexité des réductions ", Journal of complexité, 10, pp.117-138, 2001. Version préliminaire dans les procédures de l'ACM STOC 2001.

Answer 3

Artem notes dans son commentaire , la question est dénuée de sens plutôt que vous pouvez définir ce que vous voulez. Permettez-moi d'illustrer où les choses commencent à être « un peu bête ».

Certains notation: Pour deux problèmes $ P, Q $, écrire $ P \ leq_F Q $ pour une classe de fonctions $ F $ s'il y a $ f \ in F $ tel que $ P (x) = Q (f (x)) pour toutes les entrées $ $ x $ (de $ P $), qui est si $ P $ peut être $ F $ -Réduction à $ Q $. Écrire $ XC_F $ pour la classe de $ X $ problèmes COMPLETES par rapport à $ F $, qui est

$ \ qquad \ displaystyle XC_F = \ {P \ X \ mid \ forall Q \ dans X. \ Q \ leq_F P \} $.

On note en outre avec $ T_X $ l'ensemble des fonctions d'exécution (asymptotiquement optimales) des algorithmes que les fonctions de calcul dans un certain ensemble $ X $.

Considérons maintenant une classe arbitraire (complexité) des problèmes $ X $ ¹. Si nous limitons l'espace de réduction de $ F $ en termes de complexité de temps - tout est possible ici - il y a à peu près deux cas:

• $ T_F \ supseteq \ Omega (T_X) $ ² -. Réductions ne sont pas solveurs plus vite que problème

  Dans ce cas, XC_F $ = X $ - ce qui est évidemment pas très intéressant pour la théorie de la complexité. Compte tenu de cette $ F $ peut être utile dans la pratique, surtout si $ T_F \ subseteq \ Theta (X) $; vous pouvez réduire tous les problèmes de $ X $ à une poignée de problèmes que vous pouvez résoudre très bien. La programmation linéaire et SAT sont des exemples typiques en raison de LP- resp hautement optimisé. SAT-solveurs.

• $ T_F \ subseteq o (X) $ - des réductions sont solveurs plus vite que problème

  Ici, les choses intéressantes peut se produire, qui est $ XC_F \ subset X $ ou XC_F \ NEQ XC_ {F '} $ pour différents espaces de réduction. Que ces faits ont des ramifications intéressantes dépend du choix de béton de $ X $ et $ F $. Notez que $ XC_F = \ emptyset $ pourrait se produire, ce qui est en soi assez intéressant.

  Les choses deviennent vraiment sans intérêt plutôt lorsque vous choisissez $ F $ si « petit » que $ \ leq_F $ est clairsemée, qui est peu de réductions sont possibles. Pensez à $ X = \ mathsf {NP} $ et $ F $ tel que T_F $ \ subseteq o (n) $; les réductions doivent réduire de manière significative et entrée tailles ne peuvent pas passer trop de temps, donc $ F $ est pas très puissant.

  Il faut toutefois souligner que même une restriction à $ T_F \ subseteq O (1) feuilles de relations significatives $; par exemple, « Est-$ x $ un entier pair? » peut être réduite à "Is $ x premier bit de $ 0"? en $ O (1) $ temps et l'espace. Il pourrait donc être intéressant d'étudier même des réductions faibles pour savoir quels problèmes sont proches que d'autres en termes de complexité de réduction; vous voyez certainement de telles différences dans $ classique \ mathsf {PNJ} = \ {NP} mathsf C_P réductions de $.

Techniquement, il y a un troisième cas, par exemple $ T_F = P $ et $ T_X = \ Theta (n ^ 3) $; dans ce cas - si $ F $ est raisonnablement riche - les commentaires sur le cas d'une application. Notez également que la question auquel cas $ F $ tombe dans peut être intéressant en lui-même: "$ \ {mathsf P = NP} $?" demande en substance si $ T_F = \ Theta (X) $ (et même si $ F = \ Theta (XC_F) $).

---

1. Pour être une classe de complexité « appropriée », il doit être une sorte de « vers le bas fermé » w.r.t. complexité.
2. $ \ circ (X) $ pour une classe de fonction $ X $ et $ \ circ $ un symbole de Landau est l'extension naturelle des symboles habituels de Landau, soit $ \ circ (X) = \ bigcup_ {f \ X } \ circ (f) $.