Course contentsShow
← Computer Science
Lesson 1903 of 2,87243. Complexity TheoryFree lesson

Alternative NP Definition: Nondeterministic TMs

Characterize NP using nondeterministic Turing machines that accept in polynomial time.

Alternative NP Definition: Nondeterministic TMs

You'll learn: How to define the complexity class NP using nondeterministic Turing machines instead of verifiers and certificates.

Two Equivalent Views of NP

You've already seen NP defined through verifiers: a language is in NP if there exists a polynomial-time verifier that can check a certificate proving membership. Now we'll see an equally valid, often more elegant definition using nondeterministic Turing machines.

The Nondeterministic TM Definition

A language L is in NP if and only if there exists a nondeterministic Turing machine that decides L in polynomial time.

What does this mean? A nondeterministic TM can "guess" choices at each step—imagine it magically choosing the right path through a maze of possibilities. If any computational path accepts the input within polynomial time (relative to input size), the input is in the language.

Why These Definitions Are Equivalent

Think of the nondeterministic machine's "guesses" as generating a certificate, and its polynomial-time computation as verifying that certificate:

  • Nondeterministic TM → Verifier: The sequence of nondeterministic choices forms the certificate; the accepting computation path is the verification process.
  • Verifier → Nondeterministic TM: The TM nondeterministically guesses the certificate, then runs the verifier deterministically to check it.

Both complete in polynomial time!

The Intuition

A nondeterministic TM explores all possible solution paths simultaneously (conceptually). If a solution exists, one path finds it in polynomial steps. This captures exactly what NP problems are about: solutions that are hard to find but easy to verify.

Key Takeaway: NP can be defined as the class of languages recognized by nondeterministic Turing machines running in polynomial time—equivalent to the verifier-based definition, but emphasizing the "guessing and checking" nature of NP problems.