Reduções de uma vez vs. reduções de Turing para definir NPC

39

Por que a maioria das pessoas prefere usar muitas reduções para definir a completude do PN em vez de, por exemplo, reduções de Turing?

Matthias
fonte

Respostas:

32

Duas razões:

(1) apenas uma questão de minimalidade: ser NPC sob muitas reduções é uma afirmação formalmente mais forte e se você obtiver a afirmação mais forte (como Karp fez e como quase sempre faz), por que não dizê-lo?

(2) Falar sobre reduções de um número gera uma hierarquia mais rica e delicada. Por exemplo, a distinção NP vs co-NP desaparece nas reduções de Turing.

Isso é semelhante em espírito ao motivo pelo qual frequentemente se usa reduções do espaço de log em vez das redimensionadas.

Noam
fonte
16
Embora (2) seja certamente verdadeiro, eu posso usar (1) para argumentar que devemos usar reduções individuais. Como a maioria das reduções de um que construímos são, de fato, reduções de um, por que não as estudamos quando elas são formalmente mais fortes e as obtemos na maioria das vezes? Eu acho que porque é mais simples não precisar provar a injetividade, mesmo que normalmente a tenhamos. Nesse sentido, talvez muitas reduções de um sejam as "reduções de Cachinhos Dourados" - a potência certa, a simplicidade certa de prova.
Joshua Grochow 18/08/10
21

Não sei se há uma preferência, mas elas são conjecturadas como noções distintas. Ou seja, a redutibilidade de Turing é conjecturada como uma noção mais forte. (Existem A e B de modo que A é T-redutível a B, mas não pode ser reduzido a B.) Um artigo que discute isso é o de Lutz e Mayordomo. Eles propõem um fortalecimento da afirmação P! = NP; aproximadamente, esse NP inclui uma quantidade não negligenciável de EXPTIME. Essa suposição permite mostrar que as duas noções de redutibilidade são distintas.

Aaron Sterling
fonte
17

Acho que a razão pela qual as pessoas preferem (para começar) muitas reduções é pedagógica - uma redução de muitas de A para B é, na verdade, uma função em strings, enquanto uma redução de Turing requer a introdução de oráculos.

Observe que a redução de Cook (tempo de polinômio Turing) e a redução de Karp-Levin (tempo de polinômio muitos-um) são conhecidas por serem distintas em E incondicionalmente, por Ko e Moore e separadamente por Watanabe (conforme referenciado no artigo de Lutz e Mayordomo na resposta de Aaron Sterling).

Joshua Grochow
fonte
7

As reduções de Turing são mais poderosas do que muitas reduções de mapeamento a esse respeito: as reduções de Turing permitem mapear um idioma para seu complemento. Como resultado, isso pode obscurecer a diferença entre (por exemplo) NP e coNP. No artigo original de Cook, ele não examinou essa distinção (o iirc Cook realmente usou fórmulas DNF em vez de CNF), mas provavelmente ficou claro rapidamente que essa era uma separação importante, e muitas reduções tornaram mais fácil lidar com isso. .

Kurt
fonte
11
Stephen Cook apontou durante sua palestra na FLoC 2010 que seu artigo de 1971 realmente afirma provar que o SAT está completo para P ^ NP sob reduções de Turing ... É claro que a formulação usual segue a mesma prova, portanto esta é uma situação de alguém reivindicando menos do que provaram! Veja 4mhz.de/cook.html para uma versão redigitada do artigo. Além disso, a frase "Não conseguimos adicionar {primos} ou {pares isomórficos de gráficos} [à lista de 4 problemas NP-completos]" sempre me faz sorrir!
András Salamon
5

para pular um pouco sobre outro ângulo / resposta aqui do AS, essa é uma pergunta em aberto (também aqui ) nas fronteiras do TCS, se as reduções de Cook ("Turing") são diferentes das reduções de Karp-Levin ("muitas-uma"), possivelmente equivalente a (principal? chave?) questões em aberto de separações de classes de complexidade. aqui está um novo resultado nesse sentido

Separando a completude do cozinheiro da integral de Karp-Levin sob uma hipótese de dureza de pior caso / Debasis Mandal, A. Pavan, Rajeswari Venugopalan (ECCC TR14-126)

Mostramos que existe uma linguagem que é Turing completa para NP, mas não uma completa para NP, sob uma hipótese de pior dureza.

vzn
fonte
4

Σ1Q .

Na teoria da complexidade, há também uma noção de "hierarquia polinomial", embora, diferentemente da hierarquia aritmética, seja apenas suposto que exista. Isso leva a classificações mais sutis do que "Esse problema é tão difícil de resolver quanto o NP?"

David Harris
fonte
3

Geralmente, a redução Many-one (Karp) é mais fácil de projetar, porque é uma forma restrita de redução que faz uma chamada e a principal tarefa envolve transformar a entrada em codificação diferente. A redução de Turing pode envolver lógica complexa. A existência de um conjunto completo para NP com redução de Turing, mas não com redução de muitos, implica que P! = NP.

Por exemplo, Insatisfação está completa para NP com redução de Cook, mas não se sabe que está completa para NP com redução de Karp. Portanto, se você provar que não há redução de Karp de SAT para UNSAT (eqivalentemente de UNSAT para SAT), você provaria que NP! = CoNP e, portanto, P! = NP.

Mohammad Al-Turkistany
fonte
você pode dar uma referência à sua última frase ou explicá-la?
Tayfun Pay
2
Expliquei minha última frase.
Mohammad Al-Turkistany 23/11