Realistische Problemstellungen sind #tex2html_wrap_inline5312#-vollständig
Next: Approximierbarkeit Up: Komplexität des Problems Previous: Polynomiell lösbare Fälle
Realistische Problemstellungen sind 
-vollständig
In [EIS76] wurde erstmals ein recht allgemeines Timetabling-Problem als -vollständig nachgewiesen. Dennoch ist dieser
Beweis nicht vollständig zufriedenstellend, da das Konstrukt ein ausgesprochen unrealistisches Stundenplanproblem verwendet.
Zahlreiche Reduktionen -vollständiger Probleme für verschiedene (einfache) Erweiterungen
des STP finden sich in [CK95a] und [dWMP93], aber auch hier werden überwiegend
unrealistische Fälle verwendet. Da die verwendeten Methoden - auch wegen der Art der Konstrukte - nicht
instruktiv bezüglich eines möglichen Lösungsverfahrens erscheinen, wird an dieser
Stelle auf eine umfassende Darstellung verzichtet. Die -Vollständigkeit des in dieser Arbeit
untersuchten Problems geht zudem auch aus der im nächsten Kapitel beschriebenen
Reduktion des Graphenfärbungsproblems hervor.
(c) Martin Loehnertz 1999