Skip to main content
Springer Nature Link
Log in

Structure in Complexity Theory

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

  • Conference proceedings
  • © 1986
Save conference proceedings
View saved research

Overview

Editors:
  1. Alan L. Selman

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

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

Access this book

Log in via an institution
Softcover Book EUR 54.49
Price includes VAT (Netherlands)
  • 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

Licence this eBook for your library

Institutional subscriptions

Explore related subjects

Discover the latest articles, books and news in related subjects.

Table of contents (28 papers)

  1. Front Matter

    Download chapter 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

  4. Randomness, relativizations, and polynomial reducibilities

    • Klaus Ambos-Spies
    Pages 23-34

  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

  8. The polynomial hierarchy and intuitionistic Bounded Arithmetic

    • Samuel R. Buss
    Pages 77-103

  9. With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy

    • Jin-yi Cai
    Pages 104-104

  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

  14. Resource-bounded Kolmogorov complexity of hard languages

    • Dung T. Huynh
    Pages 184-195

  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

  19. A depth-size tradeoff for boolean circuits with unbounded fan-in

    • James F. Lynch
    Pages 234-248

  20. An optimal lower bound for turing machines with one work tape and a two-way input tape

    • Wolfgang Maass, Georg Schnitger
    Pages 249-264
Back to top

Accessibility Information

Accessibility information for this book is coming soon. We're working to make it available as quickly as possible. Thank you for your patience.

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

Keywords

Publish with us

Policies and ethics

Back to top