BEGIN:VCALENDAR
VERSION:2.0
PRODID:ILLC Website
BEGIN:VEVENT
UID:/NewsandEvents/Events/Conferences/newsitem/104
0/10-13-April-2006-New-Directions-in-Proof-Complex
ity-Isaac-Newton-Institute-for-Mathematical-Scienc
es-Cambridge-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 \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

\n \n \n For more informat
ion, see\n ht
tp://www.newton.cam.ac.uk/programmes/LAA/laaw04.ht
ml\n

\n
URL:/NewsandEvents/Events/Conferences/newsitem/104
0/10-13-April-2006-New-Directions-in-Proof-Complex
ity-Isaac-Newton-Institute-for-Mathematical-Scienc
es-Cambridge-UK
END:VEVENT
END:VCALENDAR