Praktischer Aspekt
- Ist alles mit einem Computer berechenbar?
- Ist jedes prinzipiell lösbare Problem in praktisch akzeptabler Zeit auf einem Computer bearbeitbar?
Zu 1: Ist alles mit einem Computer berechenbar?
Nein!
Nicht berechenbar bleibt zum Beispiel das Wetter und das
Verhalten vieler Individuen. Aber auch im Bereich der
Informatik selbst gibt es nicht berechenbare Probleme
(Bsp.: Halteproblem).
Zu 2: Ist jedes prinzipiell lösbare Problem in praktisch akzeptabler Zeit auf einem Computer bearbeitbar?
Hier gibt es neben den Problemen, die ein akzeptables Zeitverhalten (konstanter, linearer oder polynomialer Zeitaufwand) auch solche, bei denen die Rechenzeit so groß wäre, dass sich das Warten auf das Ergebnis nicht lohnen würde. Man wird also einen Turm von Hanoi, der aus 64 Scheiben besteht, nicht in einer akzeptablen Zeit umschichten können. Man hat wenig davon, wenn man die verschlüsselte Kommunikation über die Entwicklung eines neuen Formel-1-Motors mithört, für das Brechen des Codes aber 100 Jahre braucht.
Zusätzliche Informationen
| P-Probleme
|
NP-Probleme
|
unlösbare Probleme
|
| Probleme, die durch einen
deterministischen Algorithmus in polynomialer
Zeitabhängigkeit gelöst werden.
(es gibt eine Lösung mit akzeptablem Zeitverhalten) |
Probleme, die durch einen
nicht-deterministischen Algorithmus in polynomialer
Zeitabhängigkeit gelöst werden.
(es gibt eine Lösung, das Zeitverhalten bereitet Probleme) Näherungslösungen: Man versucht eine Lösung zu erraten und prüft die Lösungseigenschaften in polynomialer Zeitabhängigkeit. |
Probleme die durch keinen
Algorithmus gelöst werden.
|
Beispiele:
|
Beispiele:
|
Beispiel:
|
| deterministisch:
Zu jedem Zeitpunkt stehen fest: Operanden, Operation und Folgeoperation. nichtdeterministisch: Zu wenigstens einem Zeitpunkt wird wenigstens eines (Operanden, Operation und Folgeoperation) zufällig bestimmt. |