An arithmetic for polynomial-time computation

DOI10.1016/j.tcs.2006.03.019zbMath1118.03052MaRDI QIDQ2500489

Helmut Schwichtenberg

Publication date: 16 August 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.03.019

zbMATH Keywords

ramification; polynomial-time; linear Heyting arithmetic

Mathematics Subject Classification ID

03F30: First-order arithmetic and fragments

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

68N30: Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)

Related Items

Complexity Analysis by Rewriting, Introduction to clarithmetic. I, Quantum implicit computational complexity, An abstract approach to stratification in linear logic, Build your own clarithmetic I: Setup and completeness

Cites Work

• The realm of primitive recursion
• Bounded arithmetic for NC, ALogTIME, L and NL
• A new recursion-theoretic characterization of the polytime functions
• Light linear logic
• Higher type recursion, ramification and polynomial time
• Elementary arithmetic
• An arithmetic for non-size-increasing polynomial-time computation
• Metamathematical investigation of intuitionistic arithmetic and analysis. With contributions by C. A. Smorynski, J. I. Zucker and W. A. Howard
• ÜBER EINE BISHER NOCH NICHT BENÜTZTE ERWEITERUNG DES FINITEN STANDPUNKTES
• A new “feasible” arithmetic
• A syntactical analysis of non-size-increasing polynomial time computation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item