Some consequences of non-uniform conditions on uniform classes

Research output: Contribution to journalArticle

Abstract

We obtain some results of the form: If certain complexity classes satisfy a non-uniform condition, then some unlikely consequences follow. More precisely: 1. (1) If the 'non-uniform polynomial-time hierarchy' collapses at level i>0, i.e., Σi poly = Πi poly, then the Meyer-Stockmeyer hierarchy collapses at level i + 2, i.e., Σi+2 = Πi+2. This strengthens a generalization of a result of Karp and Lipton (1980). 2. (2) If co-NP is conjunctively reducible to a sparse set, then P = NP. This generalizes a theorem of Fortune (1979). 3. (3) If NP is conjunctively and disjunctively reducible to a sparse NP-complete set, then P = NP. This is a partial generalization of a result of Mahaney (1980). Conjuctive and disjunctive reducibility were introduced by Ladner, Lynch and Selman (1975). 4. (4) If co-NP is γ-reducible to a sparse set, then NP = co-NP. γ-reducibility was introduced 5. by Adleman and Manders (1977).

Original languageEnglish (US)
Pages (from-to)287-300
Number of pages14
JournalTheoretical Computer Science
Volume26
Issue number3
DOIs
StatePublished - Oct 1983

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Some consequences of non-uniform conditions on uniform classes'. Together they form a unique fingerprint.

  • Cite this