Pode-se mostrar dureza NP por reduções de Turing?

No artigo Complexidade do Problema de Frobenius, de Ramírez-Alfonsín, um problema foi comprovado como NP-completo usando reduções de Turing. Isso é possível? Como exatamente? Eu pensei que isso só era possível por um tempo polinomial de muitas reduções. Há alguma referência sobre isso?

Existem duas noções diferentes de dureza NP, mesmo a completude NP? Mas então eu estou confuso, porque, do ponto de vista prático, se eu quero mostrar que meu problema é NP-difícil, qual uso?

Eles começaram a descrição da seguinte maneira:

Um tempo polinomial Redução de Turing de um problema para outro problema é um algoritmo A que resolve usando uma subrotina hipotética A 'para resolver modo que, se A' fosse um algoritmo de tempo polinomial para , A seria um tempo polinomial algoritmo para . Dizemos que pode ser Turing reduzido para . $P_1$ $P_2$ $P_1$ $P_2$ $P_2$ $P_1$ $P_1$ $P_2$

Um problema é chamado (Turing) NP-hard se houver um problema de decisão completo NP modo que possa ser Turing reduzido para . $P_1$ $P_2$ $P_2$ $P_1$

E então eles usam essa redução de Turing de um problema NP-completo para mostrar a completude NP de algum outro problema.

complexity-theory time-complexity np-complete reductions user2145167
fonte

Respostas:

Existem (pelo menos) duas noções diferentes de dureza NP. A noção de costume, que utiliza reduções Karp, afirma que uma linguagem é NP-difícil se todas as línguas NP Karp-se reduz a . Se alterarmos as reduções de Karp para reduções de Cook, teremos uma noção diferente. Cada idioma que é Karp-NP-hard também é Cook-NP-hard, mas o inverso é provavelmente falso. Suponha que NP é diferente de coNP, e tomar o seu idioma NP-completos favorito . Então, o complemento de é difícil para Cook-NP, mas não para Karp-NP. $L$ $L$ $L$ $L$

A razão pela qual é difícil para o Cook-NP é a seguinte: use qualquer idioma no NP. Como é NP-difícil, existe uma função polytime tal que se e se . Uma redução de Cook de para pega , calcula , verifica se e gera o inverso. $\overline{L}$ $M$ $L$ $f$ $x \in M$ $f(x) \in L$ $f(x) \notin \overline{L}$ $M$ $\overline{L}$ $x$ $f(x)$ $f(x) \in \overline{L}$

O motivo pelo qual não é difícil para o NP (assumindo que o NP seja diferente do coNP) é o seguinte. Suponha que seja NP-difícil. Então, para cada idioma no coNP, há uma redução de politempo tal que se ou, em outras palavras, iff . Como está em NP, isso mostra que está em NP e, portanto, coNP NP. Isso implica imediatamente que NP coNP e, portanto, NP = 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$ $\subseteq$

Se alguma linguagem Cook-NP-hard está em P, então P = NP: para qualquer linguagem em NP, utilize a redução Cook para dar um algoritmo polytime para . Portanto, nesse sentido, as linguagens completas do Cook-NP também são "as mais difíceis do NP". Por outro lado, é fácil ver que Cook-NP-hard = Cook-coNP-hard: uma redução de Cook para pode ser convertida em uma redução de Cook para . Portanto, perdemos alguma precisão usando as reduções do Cook. $L$ $M$ $L$ $M$ $L$ $\overline{L}$

Provavelmente existem outras falhas no uso das reduções do Cook, mas deixarei isso para outros respondentes.

Yuval Filmus
fonte

Ainda não entendi completamente tudo isso, devo dizer. Mas eu tenho outra pergunta, talvez você possa responder a isso (já que não existem tantas outras respostas): e se eu tiver um vermelho de Turing. do problema NP-completo A a algum problema B e um vermelho Karp. do problema B ao problema C. Isso estabelece a completude da NP do problema C (a associação não é problema)? E, em geral, posso chamar o problema de B NP-hard ou melhor (Turing) NP-hard? Obrigado!

usar o seguinte comando

Duas reduções de Karp compõem uma redução de Karp e duas reduções de Cook compõem uma redução de Cook. Como uma redução de Karp também é uma redução de Cook, se você compõe uma redução de Karp e uma redução de Cook, obtém uma redução de Cook. Mas, em geral, você não recebe uma redução de 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$

Isso é bom. Uma redução de Turing em tempo polinomial é uma redução de Cook (como no teorema de Cook-Levin) e a redução de um problema de NP completo para o novo problema fornece dureza de NP (assim como uma redução de muitos polinômios no tempo, redução de AKA Karp). De fato, as reduções de Karp são apenas restritas às reduções de Turing.

Onde eles diferem (no que diz respeito a esta questão) está em mostrar associação. Uma redução de Karp de um problema para um problema no NP mostra que o primeiro está no NP. Uma redução de Cook na mesma direção não.

Luke Mathieson
fonte

Obrigado. Eu nem sabia que alguém mostra associação usando explicitamente uma redução de Karp. Mas faz sentido. Mas é possível mostrar a associação ao NP usando reduções de Turing nas duas direções, certo?

usar o seguinte comando

@ user2145167 não, a resposta de Yuval fornece a história completa aqui, mas, em suma, as reduções de Cook são mais fracas, portanto permita mais - por exemplo, você pode passar de qualquer problema de co-NP via redução de Cook a qualquer problema de NP completo, o que não é verdadeiro para reduções de Karp.

Luke Mathieson