↓ Skip to main content

Structure in Complexity Theory

Overview of attention for book
Cover of 'Structure in Complexity Theory'

Table of Contents

  1. Altmetric Badge
    Book Overview
  2. Altmetric Badge
    Chapter 85 The complexity of sparse sets in P
  3. Altmetric Badge
    Chapter 86 Isomorphisms and 1-L reductions
  4. Altmetric Badge
    Chapter 87 Randomness, relativizations, and polynomial reducibilities
  5. Altmetric Badge
    Chapter 88 On non-uniform polynomial space
  6. Altmetric Badge
    Chapter 89 One-way functions and circuit complexity
  7. Altmetric Badge
    Chapter 90 Relativized alternation
  8. Altmetric Badge
    Chapter 91 The polynomial hierarchy and intuitionistic Bounded Arithmetic
  9. Altmetric Badge
    Chapter 92 With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
  10. Altmetric Badge
    Chapter 93 The boolean hierarchy: Hardware over NP
  11. Altmetric Badge
    Chapter 94 Exponential time and bounded arithmetic
  12. Altmetric Badge
    Chapter 95 Probabilistic game automata
  13. Altmetric Badge
    Chapter 96 Two lower bound arguments with "inaccessible" numbers
  14. Altmetric Badge
    Chapter 97 Resource-bounded Kolmogorov complexity of hard languages
  15. Altmetric Badge
    Chapter 98 A note on one-way functions and polynomial time isomorphisms
  16. Altmetric Badge
    Chapter 99 What is a hard instance of a computational problem?
  17. Altmetric Badge
    Chapter 100 The complexity of optimization problems
  18. Altmetric Badge
    Chapter 101 The power of the queue
  19. Altmetric Badge
    Chapter 102 A depth-size tradeoff for boolean circuits with unbounded fan-in
  20. Altmetric Badge
    Chapter 103 An optimal lower bound for turing machines with one work tape and a two-way input tape
  21. Altmetric Badge
    Chapter 104 Separation results for bounded alternation
  22. Altmetric Badge
    Chapter 105 Parallel computation with threshold functions
  23. Altmetric Badge
    Chapter 106 The topology of provability in complexity theory
  24. Altmetric Badge
    Chapter 107 Optimal approximations of complete sets
  25. Altmetric Badge
    Chapter 108 Expanders, randomness, or time versus space
  26. Altmetric Badge
    Chapter 109 Diagonalisation methods in a polynomial setting
  27. Altmetric Badge
    Chapter 110 Bounded oracles and complexity classes inside linear space
  28. Altmetric Badge
    Chapter 111 Parallel computation and the NC hierarchy relativized
  29. Altmetric Badge
    Chapter 112 Probabilistic quantifiers, adversaries, and complexity classes : An overview
Overall attention for this book and its chapters
Altmetric Badge

Mentioned by

blogs
1 blog
twitter
1 X user
wikipedia
1 Wikipedia page
You are seeing a free-to-access but limited selection of the activity Altmetric has collected about this research output. Click here to find out more.
Title
Structure in Complexity Theory
Published by
Springer Berlin Heidelberg, January 2006
DOI 10.1007/3-540-16486-3
ISBNs
978-3-54-016486-9, 978-3-54-039825-7
Editors

Selman, Alan L.

X Demographics

X Demographics

The data shown below were collected from the profile of 1 X user who shared this research output. Click here to find out more about how the information was compiled.