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 . $\mathsf{NP}$ $\mathsf{AC^0}$

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

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

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

— Kaveh
źródło

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ć.

— Robin Kothari,

@ Robin, dzięki, sprawdzę Redukcje złożoności obwodu: twierdzenie o izomorfizmie i twierdzenie o luce .

— Kaveh

@ Robin, myślę, że pozytywnie odpowiada na moje pytanie: „ Twierdzenie 10. (Twierdzenie luki) Niech C będzie dowolną odpowiednią klasą złożoności. Zestawy trudne dla C przy nierównomiernych redukcjach AC0 są trudne dla C przy nierównomiernych redukcjach NC0 ”. oraz „ Następstwem 4. Dla każdej właściwej klasy złożoności C każdy zestaw kompletny dla C w ramach redukcji NC0 jest kompletny w ramach redukcji obliczanych na podstawie głębokości dwóch obwodów AC0 i odwracalnych na głębokości trzech obwodów AC0. ” gdzie właściwe środki „ zamknięte w ramach DLogTime jednolitych redukcji NC1 „. Czy chcesz opublikować odpowiedź, aby ją zaakceptować?

— Kaveh

Ok, opublikuję to ponownie.

— Robin Kothari,

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ć.

— Robin Kothari
źródło