History


Help on query formulation
Practically unsolvable problems. (Praktisch unlösbare Probleme.) (German)
Log In 14, No. 4, 16-21 (1994).
Zu den fundamentalen Ideen der Informatik im Zusammenhang mit der Bewertung von Algorithmen gehört ihre Komplexität. Programme und Algorithmen, die man in der Praxis verwendet, sollten möglichst effizient arbeiten, d.h., sie sollten ein vorgegebenes Problem in möglichst kurzer Zeit und mit möglichst geringem Einsatz an Betriebsmitteln (vor allem Speicherplatz) lösen. Wir werden uns in diesem Beitrag mit einer Klasse von sogenannten harten Problemen befassen, für die man bisher keine effizienten Algorithmen kennt.
Classification: P50
Valid XHTML 1.0 Transitional Valid CSS!