TY - GEN

T1 - On strong separations from AC°

AU - Allender, Eric

AU - Gore, Vivek

N1 - Funding Information:
Recall that a set L is immune to a class C if L is infinite and has no infinite subset in C. Immunity is of interest in complexity theory because it provides a characterization of problems all of whose instances are complex [BS85]; such languages define the 1 Supported in part by NSF grant CCR-9000045. 2 Supported in part by a DIMACS research asslstantshlp.
Funding Information:
DIMACS is an NSF Science and Technology Center, funded under contract STC-88-09648; and also receives support from tile New Jersey Comr~ission on Science and Teclmology.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1991.

PY - 1991

Y1 - 1991

N2 - We investigate sets that are immune to AC0; that is, sets with no infinite subset in AC0. First we show that such sets exist in Ppp. Although this seems like a rather weak result (since AC0 is an extremely weak complexity class and Ppp contains the entire polynomial hierarchy) we also prove a somewhat surprising theorem, showing that a significant breakthrough will be necessary in order to prove a bound much better than Ppp. Namely, we show that any answer to the question: Are there sets in NP that are immune to AC0? will provide non-relativizable proof techniques suitable for attacking the Ntime vs Dtime question. We also show the related result that ACC is properly contained in PP, and that there is no uniform family of ACC circuits that computes the permanent of two matrices. This seems to be the first example of a lower bound in circuit complexity where the uniformity condition is essential; it is still unknown if there is any set in Dtime(2n0(1) ) that does not have non-uniform ACC circuits.

AB - We investigate sets that are immune to AC0; that is, sets with no infinite subset in AC0. First we show that such sets exist in Ppp. Although this seems like a rather weak result (since AC0 is an extremely weak complexity class and Ppp contains the entire polynomial hierarchy) we also prove a somewhat surprising theorem, showing that a significant breakthrough will be necessary in order to prove a bound much better than Ppp. Namely, we show that any answer to the question: Are there sets in NP that are immune to AC0? will provide non-relativizable proof techniques suitable for attacking the Ntime vs Dtime question. We also show the related result that ACC is properly contained in PP, and that there is no uniform family of ACC circuits that computes the permanent of two matrices. This seems to be the first example of a lower bound in circuit complexity where the uniformity condition is essential; it is still unknown if there is any set in Dtime(2n0(1) ) that does not have non-uniform ACC circuits.

UR - http://www.scopus.com/inward/record.url?scp=0346196180&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0346196180&partnerID=8YFLogxK

U2 - 10.1007/3-540-54458-5_44

DO - 10.1007/3-540-54458-5_44

M3 - Conference contribution

AN - SCOPUS:0346196180

SN - 9783540544586

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 15

BT - Fundamentals of Computation Theory - 8th International Conference, FCT 1991, Proceedings

A2 - Budach, Lothar

PB - Springer Verlag

T2 - 8th International Conference on Fundamentals of Computation Theory, FCT 1991

Y2 - 9 September 1991 through 13 September 1991

ER -