Trade-off-Sätze

In diesen Sätzen geht es um die Frage, ob eine Größe (Raum, Zeit, Nichtdeterminismus) durch eine andere ersetzt werden kann. Ich zeige:

• Nichtdeterminismus kann nicht durch einen ,,geringen`` Zeitverlust ausgeglichen werden (Folgerung aus Satz 5.1). (Selbstverständlich kann Nichtdeterminismus immer durch exponentiellen Zeitverlust ausgeglichen werden.) Andererseits kann man Zeit durch eine gleiche Menge von Nichtdeterminismus ersetzen (Satz 5.7). Der Beweis dieses Satzes beinhaltet eine technisch sehr aufwendige Simulation. Insbesondere mußte ich einen neuen Berechnenbarkeitsbegriff (Definition 5.5) einführen. Nichtdeterminismus ist also mächtiger als Zeit.
• In Abschnitt 5.6 wird das Verhältnis von Nichtdeterminismus und Raum untersucht. Die Sätze 5.15 und 5.16 zeigen, daß prinzipiell linearer Zeitverlust in Kauf genommen werden muß. Die Sätze 5.17 und 5.20 zeigen, daß bei passender Speichergeometrie linearer Zeitverlust auch ausreichend ist. (Insbesondere, die in Satz 5.16 bewiesene Simulation, ist recht aufwending.)
• Satz 5.13 zeigt, daß Nichtdeterminismus nicht dazu verwendet werden kann, um die Speicherdimension zu senken. Bei einer Zeitbeschränkung auf Realzeit sind daher Speicher und Nichtdeterminismus ,,unvergleichbare`` Größen.