Zur Aufklärung des Verhältnisses von P und NP stellt man polynomial zeitbeschränkten Turingmaschinen Zusatzinformationen - Orakel - zur Verfügung, zu deren Berechnung keine Ressourcen verbraucht werden, und untersucht, in welchem Maße sich dadurch ihre Leistungskraft steigern läßt. Ist P eine echte Teilmenge von NP, dann erhält man auf diese Weise eine Hierarchie - Polynomialzeithierarchie - interessanter Komplexitätsklassen.