## Proceedings, Structure in Complexity Theory: Fourth Annual ConferencePapers from the Fourth Annual Conference, held June 1989, Eugene, OR. Twenty-five papers on recent research in the field. Acidic paper; no index. Annotation copyright Book News, Inc. Portland, Or. |

### 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

### Common terms and phrases

accepting paths algorithm boolean function Circuit Value circuit value problem 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 function f 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 P/poly permutation group plexity 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