Reduções de um-número e reduções de Turing definem o mesmo NPC de classe

11

Gostaria de saber se as classes de NPCs definidas por muitas reduções de um e reduções de Turing são iguais.

Edit: Outra pergunta, são as reduções de Turing apenas colapsando as classes C e co-C para alguns C ou existe uma classe como existe um problema que não esteja em C ∪ c o - C sob redução de Karp e que esteja em C sob redução de Turing ?CC∪co-CC

cc.complexity-theory np-hardness reductions Ludovic Patey
fonte
4
Você leu en.wikipedia.org/wiki/… ?
Jukka Suomela
Obrigado pelo seu link. Ele responde à primeira parte da minha pergunta, mas não responde se há problemas que não estão em co-C sob redução de muitos um e estão em C sob redução de Turing, para qualquer C.
Ludovic Patey
11
Desculpe, isso pode parecer uma pergunta elementar ou talvez eu não esteja pensando direito a essa hora tardia, mas estou perdendo algo no artigo da wiki. O artigo diz que, nas reduções de Cook, NP-complete é igual a co-NP-complete, mas não o vejo. NP-hard é igual a co-NP-hard wrt Reduções de Cook, mas NP-complete significa ser NP-hard e NP , e não vejo por que (por exemplo) TAUT estaria em NP? Ou seja, TAUT é co-NP-difícil nas reduções de Cook, mas isso não é suficiente para ser NP-completo.
Kaveh
@ Monoid, você deve reformular sua pergunta para refletir esse esclarecimento. Como tal, a questão é ambígua
Suresh Venkat
possível duplicata Muitas-one reduções contra reduções de Turing para definir NPC
Suresh Venkat

Respostas:

7

Dê uma olhada nesta questão e, especialmente, nesta resposta de Aaron Sterling. Em resumo: "eles são conjecturados como noções distintas".

Matthias
fonte
Eu sei que se NP! = Co-NP, elas são noções distintas porque a redução de Turing as colapsa, mas poderia haver diferenças que não seriam colapsadas, por exemplo, um problema no NPI com redução muitos e no NPC sob redução de Turing ?
Ludovic Patey
@ Monoïd: NP ≠ coNP não implica (pelo menos de uma maneira óbvia) que as duas noções de reduções sejam distintas. Receio que você esteja confundindo a classe NP (que é definida independentemente da escolha da noção de reduções) com a classe de problemas de decisão redutíveis a NP (que depende da escolha da noção de reduções).
Tsuyoshi Ito
Opa, meu comentário anterior estava errado. Se NP ≠ coNP, as duas noções de reduções são obviamente distintas (SAT é incondicionalmente redutível a Turing para UNSAT, mas SAT é muitas e uma redutível para UNSAT se e somente se NP = coNP).
Tsuyoshi Ito
10

A BP "Hierarquia Booleana" é uma hierarquia inteira de combinações de problemas de PN sob reduções de Karp, todas em P ^ NP.

Noam
fonte
9

Tanto quanto posso dizer, esta questão realmente compreende duas questões distintas, a primeira das quais aparece no título e a segunda é dada após a edição.

(1) Muitas reduções de um e reduções de Turing definem o mesmo conjunto de problemas completos de NP (ou seja, problemas que estão no NP e nos quais o SAT pode ser reduzido)? Se o NPC sob reduções de Turing é o mesmo que o NPC sob reduções numerosas ainda era um problema em aberto há sete anos, e não acredito que tenha sido fechado desde então. Consulte esta pesquisa nas notícias do ACM SIGACT de junho de 2003 para obter detalhes.

(2) Qual é a classe de problemas aos quais o SAT tem uma redução de Turing e vice-versa? Esta é a classe de problemas difíceis de NP (em reduções de Turing) que estão em P NP . Para mais informações sobre isso, consulte a resposta de Noam.

Peter Shor
fonte
link não funciona.
T ....
8

Isso não responde à sua pergunta, mas pode-se fazer a mesma pergunta para reduções mais fracas. Por exemplo, o conjunto de problemas NP-completos muda se permitirmos apenas reduções de espaço de log, ou apenas reduções de AC 0 ou mesmo NC 0 reduções de . Um fato surpreendente é que todos os problemas conhecidos de NP-completos estão completos, mesmo com reduções de NC 0 .

Referência: Agrawal, M., Allender, E. e Rudich, S. 1997 Reduções na complexidade do circuito: um teorema de isomorfismo e um teorema de lacuna.

Robin Kothari
fonte
Esta questão sobre reduções mais fracas ainda está em aberto? Se eu tiver um problema que foi NP completo com reduções de P / poli ou BPP, mas aparentemente não com reduções de P sem assumir pressupostos teóricos de números não comprovados, vale a pena anotar?
Peter Shor
@ Peter: No artigo que citei, fica em aberto se houver algum problema que seja NP-completo sob reduções de tempo polinomial que não seja NP-completo sob reduções de AC ^ 0. Esta pergunta foi respondida Reduzindo a complexidade das reduções . Eles mostram um problema que é NP-completo com reduções de ACC, mas não reduções de AC ^ 0. Nenhum desses trabalhos parece comentar sobre problemas que são NP-completos sob reduções mais fortes que o tempo polinomial, e como isso se relaciona à possibilidade de serem NP-completos sob reduções de politmo.
precisa
1

Este artigo pretende mostrar que a existência de um problema TF N EEXP que é
[suficientemente difícil de resolver com erro zero no pior caso] implica a existência de
"uma linguagem completa de Turing para NP que não seja completa para NP. "

Por outro lado, não tentei ler nenhuma das provas reivindicadas para esse resultado,
mas a Proposição 2 e / ou sua prova demonstram um mal-entendido da definição do ZPP :
Parece que eles realmente precisam de " FP pode resolver todo o F ZPP ", em vez de apenas" ZPP = P ".


fonte