Qual é a profundidade mínima necessária de redução para a dureza NP do SAT?

14

Como todos sabem, o SAT está completo para reduções de numerosas uma em tempo polinomial . Ainda há reduções completas de wrt .NPUMAC0 0

Minhas perguntas é qual é a profundidade mínima exigida para as reduções? Mais formalmente,

Qual é o menor que SAT é -hard wrt muitas reduções de um?dNPUMACd0 0

Parece-me que deve ser suficiente? Alguém conhece uma referência?UMAC20 0

Kaveh
fonte
3
De uma olhada rápida, parece que sua pergunta deve ser respondida por "Manindra Agrawal, Eric Allender, Steven Rudich, Reduções na complexidade dos circuitos: um teorema de isomorfismo e um teorema de lacunas", JCSS 57: 127-143, 1999. " Eles dizem que "provamos que todos os conjuntos completos para NP com reduções de AC0 são completos com reduções computáveis ​​por meio de dois circuitos de AC0 de profundidade". Mas posso estar faltando alguma coisa.
Robin Kothari
@ Robin, acho que responde positivamente à minha pergunta: " Teorema 10. (Teorema das lacunas) Seja C qualquer classe de complexidade adequada. Os conjuntos difíceis para C sob reduções AC0 não uniformes são difíceis para C sob reduções NC0 não uniformes " . e " Corolário 4. para cada adequada classe de complexidade C, cada conjunto completo para C sob reduções NC0 é completo sob reduções computável pela profundidade dois circuitos Ac0 e invertida pela profundidade três circuitos Ac0. " onde adequadas significa " fechado sob reduções dlogtime uniformes NC1 " Gostaria de publicá-lo como resposta para que eu possa aceitá-lo?
Kaveh
Ok, eu vou repassar.
226136 Robin Kothari

Respostas:

8

Reposicionando meu comentário:

De uma olhada rápida, parece que sua pergunta deve ser respondida por "Manindra Agrawal, Eric Allender, Steven Rudich, Reduções na complexidade do circuito: um teorema de isomorfismo e um teorema de lacuna" , JCSS 57: 127-143, 1999. " Eles dizem que "provamos que todos os conjuntos completos para NP com reduções de AC0 são completos com reduções computáveis ​​por meio de dois circuitos de AC0 de profundidade". Mas posso estar faltando alguma coisa.

Robin Kothari
fonte