Warum ist log (n) eine raumkonstruierbare Funktion?

8

Laut "Konstruierbare Funktion" , Wikipedia:

In der Komplexitätstheorie ist eine zeitkonstruierbare Funktion eine Funktion f von natürlichen Zahlen zu natürlichen Zahlen mit der Eigenschaft, dass f ( n ) von einer Turingmaschine in der Zeit der Ordnung f ( n ) aus n konstruiert werden kann .

Aber log(n) wird nicht auf natürliche Zahlen abgebildet, sondern auf reelle Zahlen.

Warum ist log(n) trotzdem eine raumkonstruierbare Funktion?

Maxime
quelle

Antworten:

12

Denn wenn wir schreiben logn Es ist entweder in einem Kontext, in dem es keine Rolle spielt (z. B. Landau-Grenzen) oder mit der impliziten Bedeutung von logn oder logn.

Es ist sicherlich nicht sinnvoll, über konstruierbare Funktionen mit realer Reichweite zu sprechen. Ich würde annehmen, dass Ihre Quelle darüber spricht logn oder logn.

schnelle Sorte
quelle