[Alta-Logic] Peripatetic seminar: 25th April, Pavel Hrubes

[Robin Cockett]

Time: 3:30pm, 25th April 2012

Place: ICT 616

Speaker:  Pavel Hrubes

Title:  Finite consistency statements

Abstarct:
Godel's incompleteness theorem is arguably the most influential result
in mathematical logic. It can be interpreted as saying that syntactic
reasoning, and perhaps any reasoning whatsoever, is incomplete. An
analogy can be drawn between the incompleteness theorem and questions
in computational complexity (such as P=NP), by means of the so-called
finite consistency statements. Finite consistency statements roughly
assert that a theory does not have a short proof of a contradiction,
and I will discuss the question whether the statements have feasible
proofs.