Concepedia

Nondeterministic Space Complexity

Nondeterministic Space Complexity is the computational resource measure that characterizes the maximum amount of memory space required by a nondeterministic Turing machine to solve a decision problem over all possible valid computation paths for inputs of a given size.

32

Publications

2.2K

Citations

61

Authors

39

Institutions

Publications per year

2017–2026

2

Parents

Publications

32

Nondeterministic Space is Closed under Complementation

Neil Immerman · SIAM Journal on Computing · 1988 · 649 citations

, , +11

PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation

Robert A. Hearn, Erik D. Demaine · Theoretical Computer Science · 2005 · 317 citations

, , +11

Two Applications of Inductive Counting for Complementation Problems

Allan Borodin, Stephen Cook, Patrick Dymond et al. · SIAM Journal on Computing · 1989 · 135 citations

, , +13

New problems complete for nondeterministic log space

Neil D. Jones, Y. Edmund Lien, William T. Laaser · Theory of Computing Systems · 1976 · 131 citations

, , +11

On parallelism in turing machines

Dexter Kozen · 1976 · 121 citations

, , +16

1–5 of 32

Authors

61

  1. AB
    Allan Borodin

    University of Toronto, Canada

    5 publications · 286 citations

    5

    h-index

  2. MT
    Martin Tompa

    University of Washington, United States

    4 publications · 246 citations

    4

    h-index

  3. VG
    Viliam Geffert

    University of Pavol Jozef Šafárik, Slovakia

    2 publications · 63 citations

    2

    h-index

  4. DK
    David Kirkpatrick

    University of British Columbia, Canada

    2 publications · 88 citations

    2

    h-index

  5. MJ
    Michael J. Fischer

    University of Illinois Chicago, United States

    2 publications · 88 citations

    2

    h-index

1–5 of 61

Institutions

39

  1. University of Toronto

    Toronto, Canada

    7 h-index

    9 publications

    474 citations

  2. University of Washington

    Seattle, United States

    5 h-index

    7 publications

    374 citations

  3. IBM (United States)

    Armonk, United States

    3 h-index

    3 publications

    198 citations

  4. University of California San Diego

    San Diego, United States

    2 h-index

    2 publications

    158 citations

  5. University of British Columbia

    Vancouver, Canada

    2 h-index

    2 publications

    88 citations

  6. Massachusetts Institute of Technology

    Cambridge, United States

    2 h-index

    5 publications

    727 citations

  7. Yale University

    New Haven, United States

    2 h-index

    2 publications

    745 citations

  8. University of Calgary

    Calgary, Canada

    2 h-index

    4 publications

    80 citations

1–8 of 39

Venues

  1. SIAM Journal on Computing

    7 publications · 1K citations

    7

    h-index

  2. Theoretical Computer Science

    5 publications · 407 citations

    5

    h-index

  3. Theory of Computing Systems

    3 publications · 155 citations

    3

    h-index

  4. Journal of Computer and System Sciences

    2 publications · 91 citations

    2

    h-index

  5. Journal of the ACM

    JACM · 2 publications · 66 citations

    2

    h-index

1–5