Complexity Theory
Current Research
Published on 26. November 1993
Book
Hardback
321 pages
978-0-521-44220-6 (ISBN)
Description
This volume brings together the recent research of a group of the invited participants in the workshop on Structure and Complexity Theory held in Dagstuhl, Germany in February 1992. The aim of the meeting was to present and discuss new developments in central, active areas of complexity theory and to formulate future goals and research directions. The eleven articles collected in this volume reflect the state of the art in complexity theory and provide a current view of the work of some of its strongest researchers.
More details
Language
English
Place of publication
Cambridge
United Kingdom
Target group
Professional and scholarly
Illustrations
Worked examples or Exercises
Dimensions
Height: 237 mm
Width: 156 mm
Thickness: 20 mm
Weight
561 gr
ISBN-13
978-0-521-44220-6 (9780521442206)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Persons
Content
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.