# What is the minimum required depth of reductions for NP-hardness of SAT?

As everyone knows, SAT is complete for $\mathsf{NP}$ w.r.t. polynomial-time many-one reductions. It is still complete w.r.t. $\mathsf{AC^0}$ many-one reductions.

My questions is what is the minimum required depth for the reductions? More formally,

What is the least $d$ such that SAT is $\mathsf{NP}$-hard w.r.t $\mathsf{AC^0_d}$ many-one reductions?

It seems to me that $\mathsf{AC^0_2}$ should be sufficient? Does anyone know a reference?

• From a quick look, it seems like your question should be answered by "Manindra Agrawal, Eric Allender, Steven Rudich, Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem, JCSS 57: 127-143, 1999." They say "we prove that all sets complete for NP under AC0 reductions are complete under reductions that are computable via depth two AC0 circuits." But I may be missing something. – Robin Kothari Jun 7 '13 at 21:57
• @Robin, thanks, I will check Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem. – Kaveh Jun 7 '13 at 22:55
• @Robin, I think it answers my question positively: "Theorem 10. (Gap Theorem) Let C be any proper complexity class. The sets hard for C under non-uniform AC0 reductions are hard for C under non-uniform NC0 reductions." and "Corollary 4. For every proper complexity class C, every set complete for C under NC0 reductions is complete under reductions computable by depth two AC0 circuits and invertible by depth three AC0 circuits." where proper means "closed under DLogTime-uniform NC1 reductions". Would you like to post it as an answer so I can accept it? – Kaveh Jun 11 '13 at 16:34
• Ok, I'll repost it. – Robin Kothari Jun 11 '13 at 17:02