Some consequences of non-uniform conditions on uniform classes

AbstractWe 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., Σipoly = Πipoly, 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 introduced5.by Adleman and Manders (1977)