Peut-on montrer la dureté NP en réduisant Turing?

Dans l'étude Complexity of the Frobenius Problem de Ramírez-Alfonsín, un problème s'est révélé être NP-complet en utilisant les réductions de Turing. Est-ce possible? De quelle façon précisément? Je pensais que cela n'était possible que par une réduction polynomiale de plusieurs fois. Y a-t-il des références à ce sujet?

Existe-t-il deux notions différentes de dureté NP, voire de complétude NP? Mais alors je suis confus, parce que d'un point de vue pratique, si je veux montrer que mon problème est NP-difficile, que dois-je utiliser?

Ils ont commencé la description comme suit:

Un temps polynomial Réduction de Turing d'un problème à un autre problème est un algorithme A qui résout en utilisant un sous-programme hypothétique A 'pour résoudre telle sorte que, si A' était un algorithme de temps polynomial pour alors A serait un algorithme de temps polynomial pour . On dit que peut être Turing réduit à . $P_1$ $P_2$ $P_1$ $P_2$ $P_2$ $P_1$ $P_1$ $P_2$

Un problème est appelé (Turing) NP-difficile s'il y a un problème de décision NP-complet tel que peut être Turing réduit à . $P_1$ $P_2$ $P_2$ $P_1$

Et puis ils utilisent une telle réduction de Turing à partir d'un problème NP-complet pour montrer NP-exhaustivité d'un autre problème.

complexity-theory time-complexity np-complete reductions user2145167
la source

Réponses:

Il existe (au moins) deux notions différentes de dureté NP. La notion habituelle, qui utilise des réductions Karp, indique qu'une langue est NP-difficile si toutes les langues NP-Karp réduit à . Si nous changeons les réductions Karp en réductions Cook, nous obtenons une notion différente. Chaque langue qui est Karp-NP-hard est aussi Cook-NP-hard, mais l'inverse est probablement faux. Supposons que NP est différent de coNP, et prenez votre langue NP-complet favori . Ensuite, le complément de est Cook-NP-hard mais pas Karp-NP-hard. $L$ $L$ $L$ $L$

La raison pour laquelle est Cook-NP-hard est la suivante: prenez n'importe quelle langue dans NP. Etant donné que est NP-dur, il existe une fonction polynomial de telle sorte que ssi ssi . Une réduction de Cook de à prend , calcule , vérifie si $\overline{L}$ $M$ $L$ $f$ $x \in M$ $f(x) \in L$ $f(x) \notin \overline{L}$ $M$ $\overline{L}$ $x$ $f(x)$ , et génère l'inverse. $f(x) \in \overline{L}$

La raison pour laquelle n'est pas NP-dur (en supposant que NP est différent de coNP) est la suivante. Supposons que était NP-dur. Ensuite , pour chaque langue dans coNP, il y a une réduction de polynomial tel que ssi , ou en d' autres termes, ssi . Puisque est dans NP, cela montre que est dans NP, et donc coNP $\overline{L}$ $\overline{L}$ $M$ $f$ $x \in \overline{M}$ $f(x) \in \overline{L}$ $x \in M$ $f(x) \in L$ $L$ $M$ $\subseteq$ NP. Cela implique immédiatement que NP coNP, et donc NP = coNP. $\subseteq$

Si une langue Cook-NP-dur est P, alors P = NP: pour toute langue dans NP, utilisez la réduction Cook pour donner un algorithme polynomial pour . Donc, dans ce sens, les langages complets Cook-NP sont également "les plus difficiles en NP". D'autre part, il est facile de voir que Cook-NP-dur = Cook-coNP dur: une réduction Faire cuire peut être converti en une réduction Laisser cuire . Nous perdons donc une certaine précision en utilisant les réductions Cook. $L$ $M$ $L$ $M$ $L$ $\overline{L}$

Il y a probablement d'autres inconvénients à utiliser les réductions Cook, mais je laisse cela aux autres répondeurs.

Yuval Filmus
la source

Je n'ai pas encore complètement compris tout cela, je dois dire. Mais j'ai une autre question, vous pouvez peut-être y répondre (car il n'y a pas tant d'autres réponses): et si j'ai un rouge de Turing. du problème NP-complet A à un problème B et un rouge Karp. du problème B au problème C. Est-ce que cela établit la complétude NP du problème C (l'appartenance n'est pas un problème)? Et en général, puis-je appeler le problème B NP-difficile ou plutôt (Turing) NP-difficile? Merci!

user2145167

Deux réductions Karp composent une réduction Karp et deux réductions Cook composent une réduction Cook. Puisqu'une réduction Karp est également une réduction Cook, si vous composez une réduction Karp et une réduction Cook, vous obtenez une réduction Cook. Mais en général, vous n'obtenez pas de réduction Karp.

Yuval Filmus

x \in M

$x \in M$

f (x) \in L

$f(x) \in L$

f (x) \notin \bar{L}

$f(x) \notin \overline{L}$

M

$M$

L

$L$

f

$f$

x \in M

$x \in M$

f (x) \in L

$f(x) \in L$

f, x

$f,x$

f (x) \in L

$f(x) \in L$

f (x) \notin \bar{L}

$f(x) \notin \overline{L}$

\bar{L}

$\overline{L}$

L

$L$

f

$f$

C'est très bien. Une réduction de Turing en temps polynomial est une réduction de Cook (comme dans le théorème de Cook-Levin) et la réduction d'un problème NP-complet au nouveau problème donne une dureté NP (tout comme une réduction plusieurs-un de polynôme-tiem, réduction AKA Karp). En effet, les réductions de Karp ne sont de toute façon que des réductions de Turing restreintes.

Là où ils diffèrent (en ce qui concerne cette question), c'est en montrant l'adhésion. Une réduction de Karp d'un problème à un problème dans NP montre que le premier est dans NP. Une réduction Cook dans la même direction ne fonctionne pas.

Luke Mathieson
la source

Merci. Je ne savais même pas que l'on montre l'adhésion en utilisant explicitement une réduction de Karp. Mais cela a du sens. Mais on peut montrer l'appartenance à NP en utilisant une réduction de Turing dans les deux sens, non?

user2145167

@ user2145167 non, la réponse de Yuval donne toute l'histoire ici, mais en bref, les réductions Cook sont plus faibles, alors permettez-en plus - par exemple, vous pouvez passer de tout problème co-NP via une réduction Cook à tout problème NP-complet, ce qui n'est pas vrai pour les réductions Karp.

Luke Mathieson