Complexity theory: current research
Klaus Ambos‐Spies, Steven Thomas Homer, Uwe Schöning · Cambridge University Press eBooks · 1993
1. Reductions to sets of low information content V. Arvind, Y. Han, L. Hemachandra, J. Kobler, A. Lozano, M. Mundhenk, M. Ogiwara, U. Schoening, R. Silvestri and T. Thierauf 2. On average P vs. average NP J. Belanger and J. Wang 3. Upper and lower bounds for certain graph accessibility problems on bounded alternating omega-branching programs C. Meinel and S. Waack 4. Bounded reductions H. Buhrman, E. Spaan and L. Torenvliet 5. On the non-uniform complexity of the graph isomorphism problem A. Lozano and J. Toran 6. The complexity of space bounded interactive proof systems A. Condon 7. Degrees of unsolvability in abstract complexity theory M. Kummer 8. Fixed parameter tractability and completeness, R. Downey and M. Fellows 9. Associative storage modification machines J. Tromp and P. van Emde Boas 10. Additional queries and algorithmically random languages R. Book 11. Promise problems and guarded access to unambiguous computation J.-Y. Cai, L. Hemachandra and J. Vyskoc.