14
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Robin Kothari Jun 7 '13 at 21:57
  • $\begingroup$ @Robin, thanks, I will check Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem. $\endgroup$ – Kaveh Jun 7 '13 at 22:55
  • $\begingroup$ @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? $\endgroup$ – Kaveh Jun 11 '13 at 16:34
  • $\begingroup$ Ok, I'll repost it. $\endgroup$ – Robin Kothari Jun 11 '13 at 17:02
8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.