5 papers
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…
Parallelism and Adaptivity in Student-Teacher Witnessing
Ondřej Ježil, Dimitrios Tsintsilidas
Student-Teacher Games are a model of computation in which a computationally restricted Student attempts to produce a string satisfying a refutable property, while an all-powerful T…
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…