Light Logics for Polynomial Time Computations April 3th

-

English
58 Pages
Read an excerpt
Gain access to the library to view online
Learn more

Description

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

  • predicative recursion

  • explicit cost

  • machine model

  • light logics

  • pr functions over


Subjects

Informations

Published by
Reads 6
Language English
Document size 15 MB
Report a problem
Light Logics for Polynomial Time Computations
Marco Gaboardi University of Pennsylvania Università di Bologna Inria Focus Team
LightLogicsforPolynomialTimeComputations
April 3th 2012 – 1 / 33
01h22/2–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