Probleme wo bewiesen ist das diese nicht in P-Time lösbar sind. Definition L heißt NP-vollständig, wenn L∈NP und L NP-schwer ist. SAT 3-SAT Vertex Cover Clique
