Skip to main content
SpringerLink
Log in
Book cover
  • Conference proceedings
  • © 1986

Structure in Complexity Theory

Proceedings of the Conference held at the University of California, Berkeley, June 2-5, 1986

Editors:

  1. Alan L. Selman
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 223)

Sections

Buy it now

Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

This is a preview of subscription content, log in via an institution to check for access.

Table of contents (28 papers)

  1. Front Matter

    PDF

  2. The complexity of sparse sets in P

    • Eric W. Allender
    Pages 1-11

  3. Isomorphisms and 1-L reductions

    • Eric W. Allender
    Pages 12-22

  5. On non-uniform polynomial space

    • J. L. Balcázar, J. Díaz, J. Gabarró
    Pages 35-50

  6. One-way functions and circuit complexity

    • R. B. Boppana, J. C. Lagarias
    Pages 51-65

  7. Relativized alternation

    • Jonathan F. Buss
    Pages 66-76

  10. The boolean hierarchy: Hardware over NP

    • Jin-yi Cai, Lane Hemachandra
    Pages 105-124

  11. Exponential time and bounded arithmetic

    • Peter Clote, Gaisi Takeuti
    Pages 125-143

  12. Probabilistic game automata

    • Anne Condon, Richard Ladner
    Pages 144-162

  13. Two lower bound arguments with "inaccessible" numbers

    • Martin Dietzfelbinger, Wolfgang Maass
    Pages 163-183

  15. A note on one-way functions and polynomial time isomorphisms

    • Ker-I Ko, Timothy J. Long, Ding-Zhu Du
    Pages 196-196

  16. What is a hard instance of a computational problem?

    • Ker-I Ko, Pekka Orponen, Uwe Schöning, Osamu Watanabe
    Pages 197-217

  17. The complexity of optimization problems

    • Mark W. Krentel
    Pages 218-218

  18. The power of the queue

    • Ming Li, Luc Longpré, Paul M. B. Vitányi
    Pages 219-233
Back to top

Keywords

Back to top

Bibliographic Information

  • Book Title: Structure in Complexity Theory

  • Book Subtitle: Proceedings of the Conference held at the University of California, Berkeley, June 2-5, 1986

  • Editors: Alan L. Selman

  • Series Title: Lecture Notes in Computer Science

  • DOI: https://doi.org/10.1007/3-540-16486-3

  • Publisher: Springer Berlin, Heidelberg

  • eBook Packages: Springer Book Archive

  • Copyright Information: Springer-Verlag Berlin Heidelberg 1986

  • Softcover ISBN: 978-3-540-16486-9Published: 01 May 1986

  • eBook ISBN: 978-3-540-39825-7Published: 13 July 2005

  • Series ISSN: 0302-9743

  • Series E-ISSN: 1611-3349

  • Edition Number: 1

  • Number of Pages: VIII, 404

  • Topics: Computation by Abstract Devices

Back to top

Publish with us

Policies and ethics

Back to top
Access via your institution

Buy it now

Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Search

Navigation