Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Publikationen / From Bounded Arithmetic to Memory Management: Use of Type Theory to Capture Complexity Classes and Space Behaviour


Inhaltsbereich

Martin Hofmann (2001)

From Bounded Arithmetic to Memory Management: Use of Type Theory to Capture Complexity Classes and Space Behaviour

In: TLCA, pp. 2-3.

Bounded arithmetic [ 3 ] is a subsystem of Peano arithmetic defining exactly the polynomial time functions. As Gödelʼs system T corresponds to Peano arithmetic Cook and Urquhartʼs system PV ω [ 4 ] corresponds to bounded arithmetic. It is a type system with the property that all definable functions are polynomial time computable.

Artikelaktionen


Funktionsleiste