Beweise n! ist voll zeitkonstruierbar

8

Wir haben gerade letzte Woche unsere Lektion "Zeitkonstruierbarkeit" im Unterricht beendet und zum Beispiel gezeigt, dass vollständig zeitkonstruierbar sind, dh es gibt eine (deterministische Mehrband-Turing-Maschine), die für n gegeben ist, hält nach genau f ( n ) Schritten an und fragt nur, ob wir jetzt beweisen könnten, dass n ! ist voll zeitkonstruierbar (und weitergegangen).nk,2nnf(n)n!

Ich bin nicht sicher, wie der Beweis abläuft, aber ich denke, er muss bis zu einem gewissen Grad Zeitkonstruierbarkeit oder eine Identität mit Fakultäten verwenden, da wir gezeigt haben, dass n k mit n k = n + i (vollständig) zeitkonstruierbar ist = k - 1 i = 1 ( n - 1 ) n i .nknknk=n+i=1i=k1(n1)ni

Hinweise wären auch sehr willkommen. Danke im Voraus.

Koptus
quelle

Antworten:

1

Nehmen wir an, wir haben am Eingang n . Unsere Komplexität ist die Länge der Eingabe (wir nehmen an, dass es L = O ( l o g n ) ist ). Multiplikation eines k Bit von L - Bit - Zahl über Standard Multiplikation nimmt O ( k l ) Operationen (auch nach der Multiplikation Anzahl von Bits in dem resultierenden , wenn O ( k + l ) ). Wir multiplizieren linear in einer Schleife von 1 bis n , um n zu erhalten !n!nL=O(logn)klO(kl)O(k+l)1nn!. So Anzahl von Operationen durch ober begrenzt sind durchgeführt . Somit ist es Raum und Zeit konstruierbar.#=L2(1+2...(n1))=L2n(n1)2=O(L22O(L))=o(L!)

Sashas
quelle
1
Das Problem ist, dass Sie beweisen müssen (eine Maschine konstruieren, "eine Beschreibung" ihrer Schritte geben - und sie dann zählen), dass die Maschine nach genau f (n) Schritten anhält, wenn n eine Eingabelänge ist . Die Obergrenze ist in diesem Fall irrelevant (weil sie sich tatsächlich unmittelbar aus dem gegebenen Beweis ergibt).
Koptus
f(n)O(f(n))f(n)