Lower bounds for the low hierarchy: Extended abstract

Eric Allender, Lane A. Hemachandra

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

3 Scopus citations

Abstract

The low hierarchy in NP [Sc-83] and the extended low hierarchy [BBS-86] have been useful in characterizing the complexity of certain interesting classes of sets. However, until now, there has been no way of judging whether or not a given lowness result is the best possible. We prove absolute lower bounds on the location of classes is the extended low hierarchy, and relativized lower bounds on the location of classes in the low hierarchy in NP. In some cases, we are able to show that the classes are lower in the hierarchies than was known previously. In almost all cases, we are able to prove that our results are essentially optimal. We also examine the interrelationships among the levels of the low hierarchies and the classes of sets reducible to or equivalent to sparse and tally sets under different notions of reducibility. We feel that these results clarify the structure underlying the low hierarchies.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 16th International Colloquium, Proceedings
EditorsMariangiola Dezani-Ciancaglini, Simonetta Ronchi Della Rocca, Giorgio Ausiello
PublisherSpringer Verlag
Pages31-45
Number of pages15
ISBN (Print)9783540513711
DOIs
StatePublished - 1989
Event16th International Colloquium on Automata, Languages and Programming, 1989 - Stresa, Italy
Duration: Jul 11 1989Jul 15 1989

Publication series

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

Other

Other16th International Colloquium on Automata, Languages and Programming, 1989
Country/TerritoryItaly
CityStresa
Period7/11/897/15/89

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Lower bounds for the low hierarchy: Extended abstract'. Together they form a unique fingerprint.

Cite this