TY - JOUR

T1 - Some consequences of non-uniform conditions on uniform classes

AU - Yap, Chee K.

N1 - Funding Information:
* This work was sugported in part by NSF Grant MCS 80-05469. ** Present address: Courant Institute of Matheinatical Sciences, 251 Mercer Street. NL’WYork, NY 10012, U.S.A.

PY - 1983/10

Y1 - 1983/10

N2 - 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).

AB - 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).

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

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

U2 - 10.1016/0304-3975(83)90020-8

DO - 10.1016/0304-3975(83)90020-8

M3 - Article

AN - SCOPUS:0000205276

SN - 0304-3975

VL - 26

SP - 287

EP - 300

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 3

ER -