Proceedings of the Ninth Annual Structure in Complexity Theory Conference: June 28 -July 21, 1994, Amsterdam, The Netherlands

Front Cover
IEEE Computer Society Press, 1994 - Amsterdam, Netherlands - 397 pages
Papers 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.

From inside the book

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

Bibliographic information