An Arithmetic Theory for the Poly-Time Random Functions

2023/01/27 by Melissa Antonelli, Antonelli, Melissa, Ugo Dal Lago +7
Computer Science · #Computational Complexity (cs.CC) #Data Management and Algorithms #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Rough Sets and Fuzzy Logic

paper · pdf · doi:10.48550/arxiv.2301.12028

openalex publication_date 2023/01/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce a new bounded theory RS¹₂ and show that the functions which are Sigma^b₁-representable in it are precisely random functions which can be computed in polynomial time. Concretely, we pass through a class of oracle functions over string, called POR, together with the theory of arithmetic RS¹₂. Then, we show that functions computed by poly-time PTMs are arithmetically characterized by a class of probabilistic bounded formulas.

Related

• Enumerating Error Bounded Polytime Algorithms Through Arithmetical Theories
• Probabilistic Recursion Theory and Implicit Computational Complexity (Long Version)
• A polytime proof of correctness of the Rabin-Miller algorithm from Fermat's little theorem
• Algorithmically random functions and effective capacities
• Randomness, pseudorandomness and models of arithmetic