Begriffe und Definitionen

Komplexität / Komplexitätsklasse:
Komplexität bezeichnet in der Informatik die „Kompliziertheit“ von Problemen, Algorithmen oder Daten. (Wikipedia: Komplexität (Informatik) Wikipedia Komplexitätsklassen(Informatik) letzter Zugriff 15.02.18 12:40) Probleme mit verschiedener Komplexität werden je nachdem welche Ressourcen zur Lösung nötig sind in unterschiedliche Klassen eingeordnet.
Deterministisch:
Ein Algorithmus ist deterministisch, wenn bei gleichen Bedingungen immer das selbe Ergebnis folgt.
deterministische Turingmaschine (DTM):
Ein Modell in der theoretischen Informatik, welche die Arbeitsweise eines Computers mathematisch modelliert und somit nachvollziehbar macht.
nichtdeterministische Turingmaschine (NTM, NDTM):
Ein theoretisches Modell, welches im Gegensatz zur DTM nicht realisierbar ist. Während eine DTM einem klar vorgegebenen Algorithmus folgt (siehe deterministisch: selbe Bedingung führt zum selben Resultat), verfolgt die NDTM mehrere „Wege“ gleichzeitig ( bei selben Bedingungen folgt nicht zwangsläufig die selbe Vorgehensweise und das selbe Ergebnis)
Komplexitätsklasse P und NP:
Die Komplexitätsklasse P beinhaltet alle Probleme, die in Polynomialzeit durch die DTM gelöst werden können. Polynomialzeit bedeutet, dass die Länge des Zeitraums in dem das Problem gelöst wird nicht mit zunehmender Komplexität exponentiell wächst. In NP befinden sich die Probleme, die von einer NDTM jedoch nicht von einer DTM in Polynomialzeit gelöst werden können.