33 citations · 176 across the 16 of their papers we have counts for
Showing 2012 · math.LOShow all
2 papers · 2 filters
math.LO2012★ 33 cited
On the computational complexity of finding hard tautologies
Jan Krajicek
It is well-known (cf. K.-Pudlák 1989) that a polynomial time algorithm finding tautologies hard for a propositional proof system exists iff is not optimal. Such an algorith…
math.LO2012★ 29 cited
A saturation property of structures obtained by forcing with a compact family of random variables
Jan Krajicek
A method how to construct Boolean-valued models of some fragments of arithmetic was developed in Krajicek (2011), with the intended applications in bounded arithmetic and proof com…