Nondeterministic Polynomial Time

Ein Entscheidungsproblem, wenn es für eine JA Antwort einen Beweis gibt, der in polynomieller Zeit verifiziert werden kann.