Konstruerbar funktion

I komplexitetsteorin är en tidskonstruerbar funktion en funktion f från naturliga tal till naturliga tal med egenskapen att f ( n ) kan konstrueras från n av en Turingmaskin i ordningens tid f ( n ). Syftet med en sådan definition är att utesluta funktioner som inte ger en övre gräns för körtiden för någon Turing-maskin.

Tidskonstruerbara definitioner

₀₀ Det finns två olika definitioner av en tidskonstruerbar funktion. I den första definitionen kallas en funktion f tidskonstruerbar om det finns ett positivt heltal n och Turingmaskin M som, givet en sträng 1 ⁿ bestående av n ettor, stannar efter exakt f ( n ) steg för alla n ≥ n . I den andra definitionen kallas en funktion f tidskonstruerbar om det finns en Turingmaskin M som, givet en sträng 1 ⁿ , matar ut den binära representationen av f ( n ) i O ( f ( n )) tid (en unär representation) kan användas istället, eftersom de två kan omvandlas i O ( f ( n )) tid).

Det finns också en föreställning om en fullt tidskonstruerbar funktion. En funktion f kallas fullt tidskonstruerbar om det finns en Turingmaskin M som, givet en sträng 1 ⁿ bestående av n ettor, stannar efter exakt f ( n ) steg. Denna definition är något mindre generell än de två första, men för de flesta tillämpningar kan båda definitionerna användas.

Utrymmeskonstruerbara definitioner

₀₀ är en funktion f rymdkonstruerbar om det finns ett positivt heltal n och en Turingmaskin M som, givet en sträng 1 ⁿ bestående av n ettor, stannar efter att ha använt exakt f ( n ) celler för alla n ≥ n . På motsvarande sätt är en funktion f rymdkonstruerbar om det finns en Turingmaskin M som, givet en sträng 1 ⁿ bestående av n ettor, matar ut den binära (eller unära) representationen av f ( n ), samtidigt som den endast använder O ( f ( n ) . )) Plats.

En funktion f är också fullt rymdkonstruerbar om det finns en Turingmaskin M som, givet en sträng 1 ⁿ bestående av n ettor, stannar efter att ha använt exakt f ( n ) celler.

Exempel

Alla vanliga funktioner f ( n ) (såsom n , n ^k , 2 ⁿ ) är tids- och rumskonstruerbara så länge som f ( n ) är åtminstone cn för en konstant c > 0. Ingen funktion som är o ( n ) kan vara tidskonstruerbar om den inte så småningom är konstant, eftersom det inte finns tillräckligt med tid för att läsa hela inmatningen. Däremot $\log(n)$ en rymdkonstruerbar funktion.

Ansökningar

Tidskonstruerbara funktioner används i resultat från komplexitetsteorin som tidshierarkisatsen . De är viktiga eftersom tidshierarkisatsen bygger på Turing-maskiner som måste avgöra i O ( f ( n )) tid om en algoritm har tagit fler än f ( n ) steg. Detta är naturligtvis omöjligt utan att kunna beräkna f ( n ) under den tiden. Sådana resultat är typiskt sant för alla naturliga funktioner f men inte nödvändigtvis sant för artificiellt konstruerade f . För att formulera dem exakt är det nödvändigt att ha en exakt definition för en naturlig funktion f för vilken satsen är sann. Tidskonstruerbara funktioner används ofta för att ge en sådan definition.

Rymdkonstruerbara funktioner används på liknande sätt, till exempel i rymdhierarkisatsen .

Den här artikeln innehåller material från constructible på PlanetMath , som är licensierad under Creative Commons Attribution/Share-Alike-licensen .