¿Cuál es la profundidad mínima requerida de reducciones para la dureza NP de SAT?

14

Como todos saben, SAT está completo para wrt polinomial-tiempo muchas reducciones de uno. Todavía está completo wrt reducciones muchos-uno.nortePAGUNC0 0

Mi pregunta es ¿cuál es la profundidad mínima requerida para las reducciones? Más formalmente,

¿Cuál es la menor tal que SAT es \ mathsf {NP} -hard wrt \ mathsf {AC ^ 0_d} reducciones de muchos?renortePAGUNCre0 0

¿Me parece que UNC20 0 debería ser suficiente? ¿Alguien sabe una referencia?

cc.complexity-theory reference-request np-hardness circuit-complexity reductions Kaveh
fuente
3
De un vistazo rápido, parece que su pregunta debería ser respondida por "Manindra Agrawal, Eric Allender, Steven Rudich, Reducciones en la complejidad del circuito: un teorema de isomorfismo y un teorema de brecha, JCSS 57: 127-143, 1999". Dicen que "demostramos que todos los conjuntos completos para NP bajo reducciones de AC0 están completos bajo reducciones que son computables a través de dos circuitos de profundidad AC0". Pero me puede faltar algo.
Robin Kothari
@ Robin, gracias, comprobaré Reducciones en la complejidad del circuito: un teorema de isomorfismo y un teorema de brecha .
Kaveh
@Robin, creo que responde positivamente a mi pregunta: " Teorema 10. (Teorema de brecha) Sea C cualquier clase de complejidad adecuada. Los conjuntos difíciles para C bajo reducciones AC0 no uniformes son difíciles para C bajo reducciones NC0 no uniformes " . y " Corolario 4. Para cada clase de complejidad apropiada C, cada conjunto completo para C bajo reducciones NC0 se completa bajo reducciones computables por profundidad dos circuitos AC0 e invertibles por profundidad tres circuitos AC0 ", donde apropiado significa " cerrado bajo reducciones DLogTime-uniforme NC1 ". ¿Desea publicarlo como respuesta para que pueda aceptarlo?
Kaveh
Ok, lo volveré a publicar.
Robin Kothari

Respuestas:

8

Volviendo a publicar mi comentario:

De un vistazo rápido, parece que su pregunta debería ser respondida por "Manindra Agrawal, Eric Allender, Steven Rudich, Reducciones en la complejidad del circuito: un teorema de isomorfismo y un teorema de brecha , JCSS 57: 127-143, 1999". Dicen que "demostramos que todos los conjuntos completos para NP bajo reducciones de AC0 están completos bajo reducciones que son computables a través de la profundidad de dos circuitos AC0". Pero me puede faltar algo.

Robin Kothari
fuente