Komplexitätsklassen P und NP
P: Die Menge aller Sprachen (Probleme), die ein deterministischer Automat in Polynomialzeit (O(P(n)) akzeptiert (löst).
NP: Die Menge aller Sprachen (Probleme), die ein nicht-deterministischer Automat in Polynomialzeit akzeptiert (löst).