BEGIN:VCALENDAR
VERSION:2.0
PRODID:ILLC Website
X-WR-TIMEZONE:Europe/Amsterdam
BEGIN:VTIMEZONE
TZID:Europe/Amsterdam
X-LIC-LOCATION:Europe/Amsterdam
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:19700329T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:19701025T030000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:/NewsandEvents/Archives/2006/newsitem/1040/10-
 13-April-2006-New-Directions-in-Proof-Complexity-I
 saac-Newton-Institute-for-Mathematical-Sciences-Ca
 mbridge-UK
DTSTAMP:20051103T000000
SUMMARY:New Directions in Proof Complexity, Isaac 
 Newton Institute for Mathematical Sciences, Cambri
 dge, UK
DTSTART;VALUE=DATE:20060410
DTEND;VALUE=DATE:20060413
LOCATION:Isaac Newton Institute for Mathematical S
 ciences, Cambridge, UK
DESCRIPTION:Proof complexity is an area of mathema
 tics (and mathematical logic and computational com
 plexity theory in particular) centered around the 
 problem whether the complexity class NP is closed 
 under complementation. With a suitable general def
 inition of a propositional proof system (Cook and 
 Reckhow 1979) this becomes a lengths-of-proofs que
 stion: Is there a propositional proof system in wh
 ich every tautology admits a proof whose length is
  bounded above by a polynomial in the length of th
 e tautology? The ultimate goal of proof complexity
  is to show that there is no such proof system; th
 at is, to demonstrate superpolynomial lower bounds
  for all proof systems.    For more information, s
 ee http://www.newton.cam.ac.uk/programmes/LAA/laaw
 04.html
X-ALT-DESC;FMTTYPE=text/html:\n      <p>\n        
 Proof complexity is an area of mathematics (and\n 
        mathematical logic and computational comple
 xity theory in particular)  \n        centered aro
 und the problem whether the complexity class NP is
  closed\n        under complementation. With a sui
 table general definition of a\n        proposition
 al proof system (Cook and Reckhow 1979) this becom
 es a\n        lengths-of-proofs question: Is there
  a propositional proof system in which\n        ev
 ery tautology admits a proof whose length is bound
 ed above by a\n        polynomial in the length of
  the tautology? The ultimate goal of proof\n      
   complexity is to show that there is no such proo
 f system; that is, to\n        demonstrate superpo
 lynomial lower bounds for all proof systems.\n    
   </p>\n    \n      <p>\n        For more informat
 ion, see\n       <a target="_blank" href="http://w
 ww.newton.cam.ac.uk/programmes/LAA/laaw04.html">ht
 tp://www.newton.cam.ac.uk/programmes/LAA/laaw04.ht
 ml</a>\n      </p>\n    
URL:/NewsandEvents/Archives/2006/newsitem/1040/10-
 13-April-2006-New-Directions-in-Proof-Complexity-I
 saac-Newton-Institute-for-Mathematical-Sciences-Ca
 mbridge-UK
END:VEVENT
END:VCALENDAR