Complexity Theory: Current Research - Rilegato

Rilegato

ISBN 10: 0521442206 ISBN 13: 9780521442206

Casa editrice: Cambridge University Press, 1993

Riassunto

This volume contains current research in computational complexity theory.

Su questo libro

Descrizione del libro

This volume contains current research in computational complexity theory, the area of theoretical computer science which studies the computational resources necessary to solve computational problems.

Contenuti

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.

Dettagli dell?edizione

• Editore: Cambridge University Press
• Data di pubblicazione: 1993
• ISBN 10: 0521442206
• ISBN 13: 9780521442206
• Rilegatura: Copertina rigida
• Lingua: Inglese
• Numero di pagine: 321
• Redattore: Ambos-Spies Klaus, Homer Steven, Schoening Uwe
• Contatto del produttore: non disponibile