ProceedingsComputer Society Press of the IEEE, 1987 - Computational complexity |
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 assume attribute grammar binary boolean bounded class of sets co-NP collapses complete sets complexity classes complexity theory Computer Science confined acceptor conjecture construction Corollary defined Definition denote deterministic elements exists exponential EXPTIME formula global relation graph Hartmanis Hence hierarchy IEEE implies integer isomorphism Kolmogorov complexity languages Lemma logspace m-degree membership Neil Immerman nondeterministic notion NP-complete NP-complete sets o-structures 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 satisfies Schöning self-reducible Selman sets in NP shP-minimal simulation space sparse oracles sparse set stage strings of length structure subset subspace tape Threshold Circuits tion Turing machine