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

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?

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.

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.

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).

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. .

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.

$\Sigma_1$$Q$ .

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?"

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.