## Proceedings of the Ninth Annual Structure in Complexity Theory Conference: June 28-July 1, 1994 Amsterdam, the Netherlands/94Ch3423-1Papers presented at the Ninth Annual Structure in Complexity Theory Conference, held in Amsterdam, June-July 1994. Among the topics: on the query complexity of clique size and maximum satisfiability; the complexity world below logarithmic space; on the structure of complete sets; time, hardware, and uniformity; predicate classes and promise classes; random debaters and the hardness of approximating stochastic functions; and the complexity of learning with queries. No index. Annotation copyright by Book News, Inc., Portland, OR |

### What people are saying - Write a review

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

### Contents

Approximate Sets | 12 |

On the Query Complexity of Clique Size and Maximum Satisfiability | 31 |

Using Bounded Query Classes to Separate Classes in the Exponential | 53 |

Copyright | |

18 other sections not shown

### Common terms and phrases

acceptance types algorithm assume binary Boolean Boolean circuit circuit collapses complete sets complexity classes Complexity Theory Computer Science configuration conjecture consider construction Corollary countable defined Definition denote deterministic DLOGTIME encoding exists exponential fan-in finite formula func function gate given graph guess hard hierarchy holds IEEE implies input head integer isomorphism leaf languages Lemma length live blocks logspace logspace reductions lower bound many-one many-one reduction martingale MAX3SAT NEXPTIME nodes nondeterministic Note NP-complete NP-hard O(logn optimal oracle oracle Turing machine output p-selective set P/poly path Player polynomial polynomial hierarchy polynomial-time predicate prob probabilistic Probabilistic Turing Machine probability Proc proof of Theorem proof systems properties Proposition protocol prove PSPACE PSPACE-hard recursive reductions representation class satisfying sequence simulate space bound strategy strings Structure in Complexity subset tape tion truth-table reducible Turing machine Ultrafilter unambiguous variables verifier weakly