2 citations · 4 across the 7 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
cs.CC2016★ 1 cited
Tighter Hard Instances for PPSZ
Pavel Pudlák, Dominik Scheder, Navid Talebanfard
We construct uniquely satisfiable -CNF formulas that are hard for the algorithm PPSZ. Firstly, we construct graph-instances on which "weak PPSZ" has savings of at most $(2 + ε)…
math.LO2016
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…
math.LO2016
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…