## Sparse NP-complete sets |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Definitions and Basic Results | 11 |

Structure of NP and Complete Sets | 22 |

Sparse NPComplete Sets | 37 |

3 other sections not shown

### Common terms and phrases

Boolean circuits census c(n census functions Chapter computational models computer science conjecture coNP Cook's Theorem define Definition density deterministic algorithms deterministic polynomial enumeration existence of sparse EXPTIME feasible hierarchy collapses input isomorphic Karp known NP-complete sets labelling function Lemma Let F Lipton main result many-one complete many-one reducible nodes nondeterminism nondeterministic algorithm nondeterministic polynomial nonuniform algorithm NP or PTAPE NP-hard number of strings oracle tape oracle Turing machine oracles for NP P-isomorphic to SAT polynomial size circuits polynomial time computable polynomial time hierarchy polynomial time many-one polynomial time Turing polynomial-time many-one reduction polynomially bounded problems in NP random access machine resource bounded computability satisfying assignment sets accepted sets are P-isomorphic sets for NP sets in NP solvable by polynomial sparse complete set sparse NP sparse NP-complete sets sparse oracles sparse set Theorem 3.5 thesis tion tree search method true hierarchy Turing Complete Sets Turing machine Turing reducible unsatisfiable formulas