4 papers · 1 filter
Forcing in bounded arithmetic and set theory: analogies and differences
Radek Honzik, Ondrej Ježil, Mykyta Narusevych
We provide a modern overview of several forcing methods in bounded arithmetic and compare them with forcing in set theory. We specifically discuss the countable forcing framework o…
Prime Factorization in Models of PV
Ondřej Ježil
Assuming that no family of polynomial-size Boolean circuits can factorize a constant fraction of all products of two -bit primes, we show that the bounded arithmetic theory $\te…
Feasibility of Primality in Bounded Arithmetic
Raheleh Jalali, Ondřej Ježil
We prove the correctness of the AKS algorithm \cite{AKS} within the bounded arithmetic theory or, equivalently, the first-order consequences of the theory exp…
Limits of structures and Total NP Search Problems
Ondřej Ježil
For an infinite class of finite graphs of unbounded size, we define a limit object, to be called a , relative to some computationally restricted class of funct…