Richtige Komplexitätsfunktion - Proper complexity function
Eine richtige Komplexitätsfunktion ist eine Funktion f, die eine natürliche Zahl einer natürlichen Zahl zuordnet, so dass:
- f nimmt nicht ab;
- es existiert eine k -string Turingmaschine M , so dass auf jede Eingabe der Länge n , M stoppt nach O ( n + f ( n )) Schritte verwendet O ( f ( n )) Raum und gibt f ( n ) aufeinanderfolgenden Zuschnitten .
Wenn f und g zwei richtige Komplexitätsfunktionen sind, dann sind f + g , fg und 2 f auch richtige Komplexitätsfunktionen.
Ähnliche Begriffe umfassen ehrliche Funktion, raumkonstruierbare Funktion und zeitkonstruierbare Funktion .
