Zu zeigen ist, dass sich das Problem 3-SAT in polynomiell beschränkter Zeit auf das Kunstausstellungsproblem (StarC) reduzieren lässt. Vorerst sei das Kunstausstellungsproblem vereinfacht: Wachen dürfen sich nur in den Eckpunkten des Polygons befinden. Diese Einschränkung kann am Ende aufgehoben werden. Zu jeder Instanz von 3-SAT, einer Konjunktion von Klauseln mit 3 Literalen, wird nun ein Polygon konstruiert [55].