ProceedingsSpringer-Verlag, 1990 - Computational complexity |
Contents
On Sets with Efficient Implicit Membership Tests | 11 |
On the Instance Complexity of NPHard Problems | 20 |
Session 2 | 29 |
Copyright | |
26 other sections not shown
Other editions - View all
Common terms and phrases
accepts algorithm Balcázar binary bits Boolean circuits Boolean function Boolean hierarchy characterization cheatable co-NP collapses complexity classes Complexity Theory computable function Computer Science configuration constant construction contains Corollary counting classes defined Definition denote depth deterministic DTIME(T(n encoding exists exponential EXPTIME fan-in finite formula func function f gate graph groupoid hard sequence Hemachandra IEEE input interactive proof interactive proof system language Lemma length logarithmic space LOGCFL loglog Logspace lower bound maximum order monoid NC¹ nº(¹ nondeterministic NP-complete NPNP NSAT O(log opt-L OptP oracle Turing machine output p-productive set p-superterse P/poly pebble plexity poly polynomial hierarchy polynomial time computable polynomial-time pos(t problems Proc proof systems protocol prove PSPACE quantifiers random oracle recursive reducibility relativized resp restricted result SIAM simulation span-L sparse sets strings symbols tally sets tion Turing machine unbounded fan-in uniform variables