## Proceedings, Volume 4, Part 1989 |

### What people are saying - Write a review

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

### Contents

On Polynomial Time Turing and ManyOne | 15 |

On the Theory of Average Case Complexity | 36 |

Hardness vs Randomness A Survey | 54 |

Copyright | |

17 other sections not shown

### Other editions - View all

### Common terms and phrases

accepting paths algorithm boolean function Circuit Value circuit value problem co-NP complexity classes complexity theory complexity type computable function Computer Science consider constant construction contains Corollary creative sets defined Definition denote deterministic encoding enumeration equivalent example exists exponential finite gate given graph Hartmanis Hence IEEE infinite initial segment input instance integer isomorphic iteration Kolmogorov complexity language lattice Lemma linear logarithmic lower bounds nomial nondeterministic oblivious one-way function oracle output p-completely p-completely creative p-creative permutation group plexity polynomial hierarchy polynomial time computable polynomial-time probability problem Proc program-size complexity programming system properties protocol prove PSPACE quantifier-free query hierarchy random recursion theory recursive function recursive set reducibility relativize representable requirement satisfy scatter-free self-reducibility sets in NP simulate Solomonoff space sparse set stage steps strings of length subset tape techniques tion Turing degrees Turing machine Turing reductions uniform verifier