Proceedings of the ... Annual Structure in Complexity Theory Conference, Volume 2 |
What people are saying - Write a review
We haven't found any reviews in the usual places.
Contents
On Hiding Information from an Oracle | 9 |
Polynomial Terse Sets Extended Abstract | 22 |
The Probabilistic Communication Complexity of Set Intersection Preliminary | 41 |
Copyright | |
11 other sections not shown
Other editions - View all
Common terms and phrases
accepting path algorithm attribute grammar auxiliary input binary boolean class of sets co-NP collapses complete sets complexity classes complexity theory Computer Science configuration confined acceptor conjecture construction Corollary define Definition denote deterministic deterministic Turing machine elements exists exponential EXPTIME formula given global relation graph Hartmanis Hence hierarchy IEEE implies infinite dimensional integer isomorphism Kolmogorov complexity L(Ma L(Mb L(Mi languages Lemma logspace membership Neil Immerman nondeterministic notion NP-complete one-way functions oracle machine oracle set oracle Turing machine output p-close p-isomorphic P-rankable p-selective P/poly polynomial hierarchy polynomial time computable polynomial-time predicate probabilistic problem Proposition prove PSPACE quantifier queries question r.e. sets recursive sets reducible relation over finite relativized robust self-reducible Selman sets in NP simulation sise small ranking circuits space sparse oracles sparse set stage strings of length structure subset subspace tape Threshold Circuits tion Turing machine
Bibliographic information
| Title | Proceedings of the ... Annual Structure in Complexity Theory Conference, Volume 2 |
| Contributors | IEEE Computer Society. Technical Committee on Mathematical Foundations of Computing, Northeastern University (Boston, Mass.), ACM Special Interest Group for Automata and Computability Theory |
| Publisher | IEEE Computer Society Press, 1987 |
| Original from | the University of Michigan |
| Digitized | Jan 16, 2008 |
| Export Citation | BiBTeX EndNote RefMan |