15
$\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?

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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