Complete and tractable machine-independent characterizations of second-order polytime

DOI10.46298/LMCS-21(1:5)2025MaRDI QIDQ7034353zbMATH OpenFDO

Authors Emmanuel Hainry, Bruce M. Kapron, Jean-Yves Marion, Romain Péchoux

Publication date 31 January 2025

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.46298/LMCS-21(1:5)2025

zbMATH Keywords

basic feasible functionalspolynomial timesafe recursionsecond-order functionalstiering

Mathematics Subject Classification ID

Functional programming and lambda calculus (68N18) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Cites work

• -complete decision procedures for satisfiability over the reals
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A new recursion-theoretic characterization of the polytime functions
• A tier-based typed programming language characterizing feasible functionals
• Arithmetical hierarchy and complexity of computation
• Characterizing polynomial time complexity of stream programs using interpretations
• Complete and tractable machine-independent characterizations of second-order polytime
• Complexity for type-2 relations
• Complexity theory for operators in analysis
• Functional interpretations of feasibly constructive arithmetic
• FUNCTIONAL PEARL Linear lambda calculus and PTIME-completeness
• Higher-order interpretations and program complexity
• scientific article; zbMATH DE number 439891 (Why is no real title available?)
• scientific article; zbMATH DE number 445159 (Why is no real title available?)
• scientific article; zbMATH DE number 3976377 (Why is no real title available?)
• scientific article; zbMATH DE number 65741 (Why is no real title available?)
• scientific article; zbMATH DE number 3480091 (Why is no real title available?)
• scientific article; zbMATH DE number 3305097 (Why is no real title available?)
• Intensional interpretations of functionals of finite type I
• Light linear logic
• Linear logic by levels and bounded time complexity
• On characterizations of the basic feasible functionals. I
• On the Complexity of Timetable and Multicommodity Flow Problems
• Polynomial and abstract subrecursive classes
• Polynomial Running Times for Polynomial-Time Oracle Machines
• Quasi-interpretations. A way to control resources
• Size-Change Termination and Bound Analysis
• The relative complexity of NP search problems
• The size-change principle for program termination
• Theory of higher order interpretations and application to basic feasible functions
• Type-two polynomial-time and restricted lookahead

This page was built for publication: Complete and tractable machine-independent characterizations of second-order polytime

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7034353)