Eine Sprache A gehört zur Klasse NP, wenn es ein Prädikat B(x,y) gibt, das in Zeit p(|x|), p Polynom berechnet werden kann und folgender Zusammenhang gilt:

“x gehört zu A gdw. es gibt ein y und B(x,y) = 1”

In diesem Zusammenhang sagt man auch, dass y ein Zeuge oder Beweis für die Zugehörigkeit von x zu A ist. Dieser Begriff kann verallgemeinert werden, dazu sind die folgenden Videoclips und Powerpoint-Folien vielleicht spannend.