<p>Reposting my comment:</p>

<p>From a quick look, it seems like your question should be answered by "Manindra Agrawal, Eric Allender, Steven Rudich, <a href="http://www.cse.iitk.ac.in/users/manindra/isomorphism/non-uniform-ac0-iso.pdf">Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem</a>, 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.</p>

CC BY-SA 3.0
2013-06-11T17:04:33.417Z
2013-06-11T17:04:33.417Z
Robin Kothari
<p>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.</p>

<p>My questions is what is the minimum required depth for the reductions? 
More formally, </p>

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

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

CC BY-SA 3.0
2013-06-07T21:57:18.280Z
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
CC BY-SA 3.0
2013-06-07T22:55:17.523Z
@Robin, thanks, I will check [Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem](http://ftp.cs.rutgers.edu/pub/allender/switch3.pdf).
Kaveh
CC BY-SA 3.0
2013-06-11T16:34:25.477Z
@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
CC BY-SA 3.0
2013-06-11T17:02:12.273Z
Ok, I'll repost it.
Robin Kothari
<cc.complexity-theory><reference-request><np-hardness><circuit-complexity><reductions>
What is the minimum required depth of reductions for NP-hardness of SAT?
Kaveh
# What is the minimum required depth of reductions for NP-hardness of SAT?

(Asked by: username_0 on 2013-06-07)

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?

**Tags:** cc.complexity-theory, reference-request, np-hardness, circuit-complexity, reductions
> **Comments:**
> **username_1**: 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.  
> **username_0**: @Robin, thanks, I will check [Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem](http://ftp.cs.rutgers.edu/pub/allender/switch3.pdf).  
> **username_0**: @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?  
> **username_1**: Ok, I'll repost it.  

---

## 1 answers

### Answer by username_1 on 2013-06-11. Score: 8 | Accepted answer

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](http://www.cse.iitk.ac.in/users/manindra/isomorphism/non-uniform-ac0-iso.pdf), 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.


---

