Der Satz von Fagin ist ein 1973 von Ronald Fagin bewiesener Satz aus der deskriptiven Komplexitätstheorie, der aussagt, dass die Menge aller mit Hilfe der existentiellen Prädikatenlogik zweiter Stufe beschreibbaren Sätze genau die Komplexitätsklasse NP ist. Die existentielle Prädikatenlogik zweiter Stufe enthält Sätze, bei denen über die P...