15

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?

Kaveh
  • 21,577
  • 8
  • 82
  • 183
  • 3
    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 07 '13 at 21:57
  • @Robin, thanks, I will check Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem. – Kaveh Jun 07 '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

1 Answers1

8

Reposting my comment:

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
  • 13,617
  • 2
  • 60
  • 116