28 citations · 29 across the 2 of their papers we have counts for
2 papers
cs.LO2023★ 1 cited
A proof complexity conjecture and the Incompleteness theorem
Jan Krajicek
Given a sound first-order p-time theory capable of formalizing syntax of first-order logic we define a p-time function that stretches all inputs by one bit and we use its…
cs.CC2012★ 28 cited
Pseudo-finite hard instances for a student-teacher game with a Nisan-Wigderson generator
Jan Krajíček
For an NP intersect coNP function g of the Nisan-Wigderson type and a string b outside its range we consider a two player game on a common input a to the function. One player, a co…