Light Logics for Polynomial Time Computations April 3th
58
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
58
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Niveau: Supérieur
Light Logics for Polynomial Time Computations April 3th 2012 – 1 / 33 Light Logics for Polynomial Time Computations Marco Gaboardi University of Pennsylvania Università di Bologna Inria Focus Team
Voir
Light Logics for Polynomial Time Computations April 3th 2012 – 1 / 33 Light Logics for Polynomial Time Computations Marco Gaboardi University of Pennsylvania Università di Bologna Inria Focus Team
- predicative recursion
- explicit cost
- machine model
- light logics
- pr functions over
Light Logics for Polynomial Time Computations
Marco Gaboardi University of Pennsylvania Università di Bologna Inria Focus Team
LightLogicsforPolynomialTimeComputations
April 3th 2012 1 / 33
FPTIME Boundedness StratiÞcation
Computation
Implicit Computational Complexity
ltniuOforPgicshtLoeLigmoCemiTlaimonylo3tilprsAontitapu
Implicit Computational Complexity
LightLogicsforPolynomialTimeComputations
April 3th 2012 3 / 33
Implicit Computational Complexity: Motivations
ICCaims at describingcomplexity classeswithout:
explicit reference to a speciÞc machine model without an explicit cost bound
LightLogicsforPolynomialTimeComputations
April 3th 2012 4 / 33
Implicit Computational Complexity: Motivations
ICCaims at describingcomplexity classeswithout: explicit reference to a speciÞc machine model without an explicit cost bound ItgenerallyborrowstechniquesfromMathematicalLogic: Recursion Theory, FPTIME = Predicative Recursion on Notation Structural Proof Theory,FPTIME = Bounded/Light Linear Logic Model Theory, FPTIME = PR Functions over Finite Structures
LightLogicsforPolynomialTimeComputations
April 3th 2012 4 / 33
