Word.ws English Dictionary

nondeterministic polynomial time

nondeterministic polynomial time noun: a class of decision problems for which a yes solution can be verified by a deterministic Turing machine in polynomial time, or alternatively a set of problems that can be solved in polynomial time by a nondeterministic Turing machine.

Noun

nondeterministic polynomial time (countable and uncountable, plural nondeterministic polynomial times)

  1. A class of decision problems for which a yes solution can be verified by a deterministic Turing machine in polynomial time, or alternatively a set of problems that can be solved in polynomial time by a nondeterministic Turing machine.
    Synonyms:
    NP time

Synonyms of nondeterministic polynomial time

Forms of nondeterministic polynomial time

pluralnondeterministic polynomial times

Questions about nondeterministic polynomial time

What does nondeterministic polynomial time mean?
Nondeterministic polynomial time means a class of decision problems for which a yes solution can be verified by a deterministic Turing machine in polynomial time, or alternatively a set of problems that can be solved in polynomial time by a nondeterministic Turing machine.
What part of speech is nondeterministic polynomial time?
Nondeterministic polynomial time is a noun.
What is the plural of nondeterministic polynomial time?
The plural of nondeterministic polynomial time is nondeterministic polynomial times.

Words near nondeterministic polynomial time in the dictionary

  1. nondeterminicity
  2. nondeterminism
  3. nondeterminisms
  4. nondeterminist
  5. nondeterministic
  6. nondeterministic polynomial time
  7. nondeterministic polynomial times
  8. nondeterministic Turing machine
  9. nondeterministic Turing machines
  10. nondeterministically
  11. nondeterminists

Source and license

Adapted from Wiktionary: nondeterministic polynomial time (page history and authors). Text available under the Creative Commons Attribution-ShareAlike 4.0 license. Word.ws reformatted the entry and added links. Wiktionary data of 2026-09-02.

Last updated:

Cite this entry: “nondeterministic polynomial time.” Word.ws, https://word.ws/nondeterministic_polynomial_time. Based on Wiktionary, CC BY-SA 4.0.