Concepedia

Non-deterministic Time Complexity

Non-Deterministic Time Complexity is the computational complexity measure that characterizes the maximum number of steps a non-deterministic Turing machine requires to solve a decision problem over all possible computation paths for a given input size.

19

Publications

641

Citations

42

Authors

31

Institutions

Publications per year

2017–2026

2

Parents

Publications

19

A hierarchy for nondeterministic time complexity

Stephen Cook · Journal of Computer and System Sciences · 1973 · 164 citations

, , +9

A hierarchy for nondeterministic time complexity

Stephen Cook · 1972 · 56 citations · Full text

, , +9

On the complexity of SAT

R.J. Lipton, Anastasios Viglas · 2003 · 55 citations

, , +17

Computations with a restricted number of nondeterministic steps (Extended Abstract)

Chandra M. R. Kintala, Patrick C. Fischer · 1977 · 36 citations · Full text

, , +14

Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem

Jean-Camille Birget · International Journal of Algebra and Computation · 1998 · 32 citations

, , +13

1–5 of 19

Authors

42

  1. SC
    Stephen Cook

    University of Toronto, Canada

    2 publications · 220 citations

    2

    h-index

  2. PG
    Paweł Gniewek

    University of Warsaw, Poland

    1 publications · 17 citations

    1

    h-index

  3. BM
    Barnaby Martin

    Durham University, United Kingdom

    1 publications · 15 citations

    1

    h-index

  4. IP
    Ian Pratt‐Hartmann

    University of Manchester, United Kingdom

    1 publications · 22 citations

    1

    h-index

  5. UH
    Ulrich Hertrampf

    University of Würzburg, Germany

    1 publications · 26 citations

    1

    h-index

1–5 of 42

Institutions

31

  1. Princeton University

    Princeton, United States

    3 h-index

    4 publications

    165 citations

  2. University of Toronto

    Toronto, Canada

    2 h-index

    2 publications

    220 citations

  3. Pennsylvania State University

    State College, United States

    1 h-index

    2 publications

    72 citations

  4. Shanghai Ocean University

    Shanghai, China

    1 h-index

    2 publications

    36 citations

  5. University of the Free State

    Bloemfontein, South Africa

    1 h-index

    1 publications

    23 citations

  6. Universitat Pompeu Fabra

    Barcelona, Spain

    1 h-index

    1 publications

    15 citations

  7. Nationwide Children's Hospital

    Columbus, United States

    1 h-index

    2 publications

    34 citations

  8. Battelle

    Columbus, United States

    1 h-index

    2 publications

    34 citations

1–8 of 31

Venues

  1. Journal of Computer and System Sciences

    2 publications · 190 citations

    2

    h-index

  2. eCommons (Cornell University)

    Repository · 1 publications · 19 citations

    1

    h-index

  3. BMC Bioinformatics

    1 publications · 17 citations

    1

    h-index

  4. arXiv (Cornell University)

    Repository · 1 publications · 22 citations

    1

    h-index

  5. SIAM Journal on Computing

    1 publications · 13 citations

    1

    h-index

1–5