Nondeterministic Polynomial Time Complete

Entscheidungsprobleme in $\mathcal{NP}\mathcal{C}$ gelten als besonders schwer, da es für sie keinen polynomiellen Algorithmus gibt.

Ein Entscheidungsproblem heißt Nondeterministic Polynomial Time Complete, wenn es Nondeterministic Polynomial Time ist und jedes andere Problem aus dieser Klasse auf P polynomiell reduzierbar ist Polynomielle Reduktion.

Beispiele:

• SAT
• BIP
• MIP