On strong separations from AC°

Eric Allender, Vivek Gore

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationFundamentals of Computation Theory - 8th International Conference, FCT 1991, Proceedings
EditorsLothar Budach
PublisherSpringer Verlag
Pages1-15
Number of pages15
ISBN (Print)9783540544586
DOIs
StatePublished - 1991
Event8th International Conference on Fundamentals of Computation Theory, FCT 1991 - Gosen, Germany
Duration: Sep 9 1991Sep 13 1991

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume529 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other8th International Conference on Fundamentals of Computation Theory, FCT 1991
Country/TerritoryGermany
CityGosen
Period9/9/919/13/91

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'On strong separations from AC°'. Together they form a unique fingerprint.

Cite this