Research Catalog

Complexity theory : current research

Title: Complexity theory : current research / edited by Klaus Ambos-Spies, Steven Homer, Uwe Schöning.
Publication: Cambridge ; New York : Cambridge University Press, 1993.

Items in the Library & Off-site

Filter by

1 Item

Item details
Status	Format	Access	Call Number	Item Location
Request for On-site Use Request Scan How do I pick up this item and when will it be ready?	Text	Request in advance	QA267 .C67 1993g	Off-site

Holdings

Details

Additional Authors

Description

viii, 313 pages : illustrations; 24 cm

Subject

Computational complexity

Bibliography (note)

Includes bibliographical references.

Contents

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 -- On Average P vs. Average NP / J. Belanger and J. Wang -- Additional Queries and Algorithmically Random Languages / R. Book -- Bounded Reductions / H. Buhrman, E. Spaan and L. Torenvliet -- Promise Problems and Guarded Access to Unambiguous Computation / J-Y. Cai, L. Hemachandra and J. Vyskoc -- The Complexity of Space Bounded Interactive Proof Systems / A. Condon -- Fixed Parameter Tractability and Completeness / R. Downey and M. Fellows -- Degrees of Unsolvability in Abstract Complexity Theory / M. Kummer -- On the Non-Uniform Complexity of the Graph Isomorphism Problem / A. Lozano and J. Toran -- Upper and Lower Bounds for Certain Graph Accessibility Problems on Bounded Alternating omega-Branching Programs / C. Meinel and S. Waack -- Associative Storage Modification Machines / J. Tromp and P. van Emde Boas.

ISBN

0521442206

OCLC

ocm29700026

Owning Institutions

Columbia University Libraries