Wir sagen , daß eine Funktion ist zeit konstruierbar , wenn es ein deterministisches Mehrbandturingmaschine existiert daß an allen Eingängen der Länge Fabrikate höchstens Schritte und für jeden dort eine Eingabe besteht aus Länge auf der genau Schritte macht.
Wir sagen, dass eine Funktion vollständig zeitkonstruierbar ist , wenn es eine deterministische Multi-Tape-Turing-Maschine M gibt , die auf allen Eingaben der Länge n genau f ( n ) Schritte ausführt.
F1: Gibt es eine Funktion, die zeitkonstruierbar und nicht vollständig zeitkonstruierbar ist?
Die Antwort ist ja (siehe diese Antwort ), wenn . Kann die Bedingung für "Ja" auf P ≠ N P verstärkt werden ? Kann "ja" bewiesen werden?
Frage 2: Ändert sich die Klasse der (vollständig) zeitkonstruierbaren Funktionen, wenn wir in der Definition nur 2-Band-Turing-Maschinen zulassen?
F3: Was sind die "nachweisbaren" Gründe für die Annahme, dass alle netten Funktionen vollständig zeitkonstruierbar sind?
Der Aufsatz
Kojiro Kobayashi: Über das Beweisen der Zeitkonstruierbarkeit von Funktionen. Theor. Comput. Sci. 35: 215-225 (1985)
beantwortet teilweise Q3. Die teilweise Zusammenfassung und Aktualisierung davon ist in dieser Antwort . Ich nehme Q3 als beantwortet.
In der Vergangenheit wurde der Begriff der zählbaren Echtzeitfunktion anstelle der (vollständig) zeitkonstruierbaren Funktion verwendet. Siehe diese Frage für mehr.
Antworten:
In den letzten Tagen habe ich viel über (vollständig) zeitkonstruierbare Funktionen nachgedacht und werde das, was ich herausgefunden habe, durch Beantwortung von Q1 und Q3 präsentieren. Q2 scheint zu schwer.
Q3:
Kobayashi in seinem Artikel (die Referenz in der Frage) bewiesen , dass eine Funktion , für die es ein existiert ε > 0 st f ( n ) ≥ ( 1 + ε ) n , ist voll Zeit konstruierbar iff es ist berechenbar in O ( f ( n ) ) Zeit. (Beachten Sie, dass es unerheblich ist, ob der Eingang oder der Ausgang unär / binär ist, da wir zwischen diesen beiden Darstellungen in linearer Zeit transformieren können). Dies macht die folgenden Funktionen vollständig zeitkonstruierbar: 2 n ,f:N→N ϵ>0 f(n)≥(1+ϵ)n O(f(n)) 2n , n ! , n ⌊ log n ⌋ , alle Polynome p über N st p ( n ) ≥ ( 1 + ϵ ) n ... Kobayashi erwies sich auch für einige Funktionen, die langsamer als ( 1 + ϵ ) n werden ,als vollständig zeitkonstruierbar , wie n + ⌊ ⌊ log n ⌋ q ⌋ für q ∈ Q + ...22n n! n⌊logn⌋ p N p(n)≥(1+ϵ)n (1+ϵ)n n+⌊⌊logn⌋q⌋ q∈Q+
Um mit Beispielen für vollständig zeitkonstruierbare Funktionen fortzufahren, kann man beweisen, dass wenn und f 2 vollständig zeitkonstruierbar sind, dann f 1 +f1 f2 , f 1 f 2 , f f 2 1 und f 1 ∘ f 2 sind auch vollständig zeitkonstruierbar (die spätere folgt direkt aus Satz 3.1 in Kobayashi). Insgesamt hat mich das überzeugt, dass viele nette Funktionen in der Tat vollständig zeitkonstruierbar sind.f1+f2 f1f2 ff21 f1∘f2
Es ist überraschend, dass Kobayashi keinen Weg gefunden hat, die der (netten) Funktion ⌊ n log n ⌋ vollständig zu beweisen (und ich auch nicht).⌊nlogn⌋
Lassen Sie uns auch die Definition aus dem Wikipedia-Artikel kommentieren : Eine Funktion ist zeitkonstruierbar, wenn es eine Turing-Maschine M gibt , die bei einem String 1 n f ( n ) in O ( f ( n ) ) -Zeit ausgibt .f M 1n f(n) O(f(n)) Wir sehen, dass diese Definition unserer Definition der vollständigen Zeitkonstruierbarkeit für Funktionen .f(n)≥(1+ϵ)n
Q1:
Diese Frage hat eine wirklich interessante Antwort. Ich beanspruche , dass , wenn alle Zeitfunktionen konstruierbar sind vollständig zeit konstruierbar, dann . Um dies zu beweisen, nehmen wir ein beliebiges Problem L ∈ N E X P - T I M E , L ⊆ { 0 , 1 } ∗ . Dann gibt es eine k ∈ N , st LEXP−TIME=NEXP−TIME L∈NEXP−TIME L⊆{0,1}∗ k∈N L can be solved by a NDTM M in 2nk−1 steps. We can assume that at each step M goes in at most two different states for simplicity. Now define the function
Ich behaupte, dass ist. Man betrachte die folgende deterministische Turingmaschine T :f T
Note that the length ofw (=n ) is enough that it determines all nondeterministic choices, since M on input (first ⌊⌊logn⌋+1−−−−−−−−−√k⌋ bits of bin(n)) makes at most n steps.
We can makeT run in at most 8n+1 steps. Now the following Turing machine proves that f is time-constructible:
This algorithm runs in exponential time and solvesL . Since L∈NEXP−TIME was arbitrary, EXP−TIME=NEXP−TIME .
quelle