Concepedia

Non-deterministic Polynomial Time

Non-Deterministic Polynomial Time is a computational complexity class that consists of decision problems for which a given solution can be verified by a deterministic Turing machine in polynomial time, distinguishing it from deterministic classes by allowing non-deterministic branching during computation.

148

Publications

6.6K

Citations

409

Authors

239

Institutions

Publications per year

2017–2026

64

Parents

Publications

148

Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

T. P. Baker, John Gill, Robert M Solovay · SIAM Journal on Computing · 1975 · 738 citations

, , +10

An Effective PSO-Based Memetic Algorithm for Flow Shop Scheduling

Bo Liu, Ling Wang, Yihui Jin · IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics) · 2007 · 480 citations

, , +16

Non-interactive cryptocomputing for NC/sup 1/

Tomas Sander, Adam Young, Moti Yung · 2003 · 279 citations

, , +11

Llull and Copeland Voting Computationally Resist Bribery and Constructive Control

Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra et al. · Journal of Artificial Intelligence Research · 2009 · 254 citations · Full text

, , +12

A Novel K-Means Clustering Algorithm with a Noise Algorithm for Capturing Urban Hotspots

Xiaojuan Ran, Xiangbing Zhou, Lei Mu et al. · Applied Sciences · 2021 · 233 citations · Full text

, , +13

1–5 of 148

Authors

409

  1. GI
    Gábor Ivanyos

    Hungarian Academy of Sciences, Hungary

    3 publications · 83 citations

    3

    h-index

  2. LG
    Leonid Gurvits

    Joint Institute for VLBI ERIC, Netherlands

    3 publications · 121 citations

    3

    h-index

  3. KV
    K. V. Subrahmanyam

    Chennai Mathematical Institute, India

    3 publications · 83 citations

    3

    h-index

  4. YQ
    Youming Qiao

    University of Technology Sydney, Australia

    3 publications · 83 citations

    3

    h-index

  5. MM
    M.K. Marichelvam

    Solamalai College of Engineering

    3 publications · 96 citations

    3

    h-index

1–5 of 409

Institutions

239

  1. Massachusetts Institute of Technology

    Cambridge, United States

    4 h-index

    6 publications

    339 citations

  2. Princeton University

    Princeton, United States

    4 h-index

    7 publications

    241 citations

  3. University of California, Berkeley

    Berkeley, United States

    3 h-index

    3 publications

    74 citations

  4. Pennsylvania State University

    State College, United States

    3 h-index

    4 publications

    201 citations

  5. Huazhong University of Science and Technology

    Wuhan, China

    3 h-index

    8 publications

    381 citations

  6. Solamalai College of Engineering

    Madurai, India

    3 h-index

    3 publications

    96 citations

  7. Shanghai Jiao Tong University

    Shanghai, China

    3 h-index

    8 publications

    287 citations

  8. Chinese Academy of Sciences

    Beijing, China

    3 h-index

    10 publications

    236 citations

1–8 of 239

Venues

  1. Theoretical Computer Science

    6 publications · 201 citations

    6

    h-index

  2. IEEE Access

    6 publications · 190 citations

    6

    h-index

  3. arXiv (Cornell University)

    Repository · 4 publications · 57 citations

    4

    h-index

  4. 3

    h-index

  5. SIAM Journal on Computing

    3 publications · 764 citations

    3

    h-index

1–5