40 citations · 49 across the 10 of their papers we have counts for
Showing 2014Show all
3 papers · 1 filter
math.LO2014
End-extensions of models of weak arithmetic from complexity-theoretic containments
Leszek Aleksander Kołodziejczyk
We prove that if the linear-time and polynomial-time hierarchies coincide, then every model of has a proper end-extension to a model of $Π_1(\mathbb{N}…
math.LO2014
Categorical characterizations of the natural numbers require primitive recursion
Leszek Aleksander Kołodziejczyk, Keita Yokoyama
Simpson and the second author asked whether there exists a characterization of the natural numbers by a second-order sentence which is provably categorical in the theory RCA.…
cs.LO2014★ 40 cited
Small Stone in Pool
Samuel R. Buss, Leszek Aleksander Kolodziejczyk
The Stone tautologies are known to have polynomial size resolution refutations and require exponential size regular refutations. We prove that the Stone tautologies also have polyn…