Complexity theory : current research
著者
書誌事項
Complexity theory : current research
Press Syndicate of the University of Cambridge, 1993
大学図書館所蔵 件 / 全17件
-
該当する所蔵館はありません
- すべての絞り込み条件を解除する
注記
Includes bibliographical references
内容説明・目次
内容説明
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.
目次
- 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.
「Nielsen BookData」 より
