Alternierung #3 - AP = PSpace
Wir zeigen, dass AP = PSpace ist, also die Probleme, die von einer polynomiell zeitbeschränkten alternierenden Turingmaschine gelöst werden, sind genau die Probleme, die von einer deterministischen polynomiell platzbeschränkten Turingmaschine gelöst werden können. Das ist ein interessanter Zusammenhang zwischen Alternierung, Zeitkomplexität und Platzkomplexität.