Jaka jest minimalna wymagana głębokość redukcji dla NP-twardości SAT?

Jak każdy wie, SAT jest kompletna dla wrt wielomian czasie wiele-jeden redukcje. Nadal jest kompletny z redukcjami wielokrotności A C 0 .$\mathsf{NP}$$\mathsf{AC^0}$

Moje pytania brzmi: jaka jest minimalna wymagana głębokość redukcji? Bardziej formalnie,

Co najmniej takie, że SAT jest redukcją N P- twardą wr A C 0 d wielokrotności jeden?$d$$\mathsf{NP}$$\mathsf{AC^0_d}$

Wydaje mi się, że powinno wystarczyć? Czy ktoś zna referencje?$\mathsf{AC^0_2}$

Przesłanie mojego komentarza:

Z szybkiego spojrzenia wydaje się, że na twoje pytanie powinien odpowiedzieć „Manindra Agrawal, Eric Allender, Steven Rudich, Reductions in Circuit Complexity: An Isomorphism Theorem and Gap Theorem , JCSS 57: 127-143, 1999”. Mówią „udowadniamy, że wszystkie zestawy zakończone dla NP w ramach redukcji AC0 są kompletne w ramach redukcji, które można obliczać za pomocą dwóch obwodów AC0 głębokości”. Ale coś może mi brakować.