Logic Seminar-Average case hardness of theorems and tautologies

Time: Thursday, April 14, 11:00 am-12:00 noon

Place: zoom
https://gwu-edu.zoom.us/j/97561744736

Speaker:  Hunter Monroe, Consultant, International Monetary Fund

Title: Average case hardness of theorems and tautologies

Abstract: The presentation will explore whether it is hard on average for an algorithm to recognize (and to certify this) arithmetic statements with no proof of at most t steps (this is coNP-complete, so hardness means P!=NP!=coNP). With no limit on the number of steps, Calude and Jurgensen (2005) showed that in any finitely-specified, sound, consistent theory strong enough to formalize arithmetic, the probability that a true sentence of length n is provable in the theory tends to zero when n tends to infinity, while the probability that a sentence of length n is true is strictly positive. True but unprovable statements about the incompressibility of Kolmogorov random strings drive this result. Are statements without short proofs, or equivalently families of tautologies, hard to recognize on average, or even hard with probability one asymptotically? The presentation will explore this and other analogies between the theories of noncomputability and complexity.