Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-086 | 30th June 2025 22:29

An Introduction to Feasible Mathematics and Bounded Arithmetic for Computer Scientists

RSS-Feed




TR25-086
Authors: Jiatu Li
Publication: 1st July 2025 01:31
Downloads: 373
Keywords: 


Abstract:

This note gives an in-depth discussion on feasible mathematics and bounded arithmetic with a focus on Cook's theory PV (STOC'75). We present an informal characterization of PV based on three intuitive postulates and formulate the Feasible Mathematics Thesis, which asserts the equivalence between this informal framework and the formal system PV. To support this thesis, we provide a detailed exposition demonstrating how advanced programming and reasoning tools can be systematically constructed within the seemingly weak theory PV.



ISSN 1433-8092 | Imprint