SPEAKER: David Mitchell

TITLE: How Long is a Proof of P (and Why Would I Care)?

DATE: Thursday, November 22, 2001, 12:30 p.m. - 1:30 p.m; ASB 9705

ABSTRACT:

Propositional logic is typically regarded by logicians as being trivial. Yet fundamental questions about the lengths of propositional proofs turn out to be very challenging, and also deeply connected to a number of important problems in logic and computer science.

I will give a short introduction to propositional proof systems and the study of proof complexity, and then consider how basic questions about proof complexity relate to problems in complexity theory (e.g., P=NP?), automated theorem proving, the design general search algorithms.