2 citations · 4 across the 7 of their papers we have counts for
5 papers · 1 filter
Herbrand Game Complexity
Sam Buss, Pavel Pudlák
The Student-Teacher game is an extension of Herbrand's theorem. In the game, Student and Teacher take turns giving values for existentially and universally quantified variables, an…
The canonical pairs of bounded depth Frege systems
Pavel Pudlak
The canonical pair of a proof system is the pair of disjoint NP sets where one set is the set of all satisfiable CNF formulas and the other is the set of CNF formulas that have…
A wild model of linear arithmetic and discretely ordered modules
Petr Glivický, Pavel Pudlák
Linear arithmetics are extensions of Presburger arithmetic (Pr) by one or more unary functions, each intended as multiplication by a fixed element (scalar), and containing the full…
Incompleteness in the finite domain
Pavel Pudlak
Motivated by the problem of finding finite versions of classical incompleteness theorems, we present some conjectures that go beyond . These conjectures formall…
Randomness, pseudorandomness and models of arithmetic
Pavel Pudlak
Pseudorandmness plays an important role in number theory, complexity theory and cryptography. Our aim is to use models of arithmetic to explain pseudorandomness by randomness. To t…