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

Como todos sabem, o SAT está completo para reduções de numerosas uma em tempo polinomial . Ainda há reduções completas de wrt . $\mathsf{NP}$ $\mathsf{AC^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? $d$ $\mathsf{NP}$ $\mathsf{AC^0_d}$

Parece-me que deve ser suficiente? Alguém conhece uma referência? $\mathsf{AC^0_2}$

cc.complexity-theory reference-request np-hardness circuit-complexity reductions Kaveh
fonte

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, obrigado, vou verificar reduções na complexidade do circuito: um teorema de isomorfismo e um teorema de lacuna .

Kaveh

@ 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

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

Respostas: