Feasibility of primality in bounded arithmetic

DOI10.1017/FMS.2026.10194MaRDI QIDQ7227040zbMATH OpenFDO

Authors Raheleh Jalali, Ondřej Ježil

Publication date 9 April 2026

Published in Forum of Mathematics, Sigma (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1017/FMS.2026.10194

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Factorization; primality (11A51) Polynomials in number theory (11C08) Polynomials over finite fields (11T06) Polynomial rings and ideals; rings of integer-valued polynomials (13F20)

Cites work

• Abelian groups and quadratic residues in weak arithmetic
• Bounded arithmetic and the polynomial hierarchy
• Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two
• Dual weak pigeonhole principle, Boolean complexity, and derandomization
• Feasibly constructive proofs of succinct weak circuit lower bounds
• scientific article; zbMATH DE number 3557241 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• Iterated multiplication in VTC^0
• Logical foundations of proof complexity
• Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
• Polynomial-time pseudodeterministic construction of primes
• PRIMES is in P

This page was built for publication: Feasibility of primality in bounded arithmetic

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