Enzyklopädie > E > E (Komplexitätsklasse)
E (Komplexitätsklasse)
Die Komplexitätsklasse mathbf E ist die Klasse aller Sprachen, die sich von einer deterministischen Turingmaschine in exponentieller Zeit mit linearem Exponenten lösen lassen. Es existiert also für jedes Linmathbf E eine Turingmaschine M_L mit einer Zeitschranke t_L(n)in O(k^n) für ein beliebiges kinmathbb N, so dass für alle win L die Maschine M_L das Wort w in höchstens t_L(|w|) Schritten akzeptiert.
Mehr Informationen (Wikipedia)
Die Informationen wurden von Wikipedia übernommen, einer offenen Enzyklopädie in welche Freiwillige ihre Beiträge beisteuern.
Die Texte sind unter den Bedingungen der GNU Free Documentation License zugänglich.Encyklopedie (cz) Encyklopédia (sk) Encyclopedia (en)