### 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 language | English (US) |
---|---|

Pages (from-to) | 287-300 |

Number of pages | 14 |

Journal | Theoretical Computer Science |

Volume | 26 |

Issue number | 3 |

DOIs | |

State | Published - Oct 1983 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)