Confirmed Participants Schedule (PDF) Workshop Videos
Workshop Files
Final Report (PDF) Testimonials

Proof complexity (11w5103)

Organizers

(University of California, San Diego)

(University of Toronto)

(Memorial University of Newfoundland)

(University of Toronto)

Pavel Pudlak (Mathematical Institute of the Czech Academy of Sciences)

Description

The Banff International Research Station will host the "Proof complexity" workshop from October 2nd to October 7th, 2011.




Given a theorem, how short is its shortest proof? Is it possible to find a short proof efficiently? How complex are the concepts necessary to prove this theorem? These are just some of the questions studied in the field of proof complexity. One of the motivating questions is whether there is a formal system in which every propositional tautology has a proof of length polynomial in length of the tautology. A negative answer would resolve the famous P vs. NP problem.






The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada's Natural Science and Engineering Research Council (NSERC), the U.S. National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnología (CONACYT).