slideshow 3

Logic seminar

usually takes place each Monday at 14:00 in IM, rear building, ground floor
Chair: Pavel Pudlak, Neil Thapen
More information on the old seminar web page. The programme is announced via the mailing list.

Polynomial calculus space and resolution width

Neil Thapen
Institute of Mathematics
Monday, 25. February 2019 - 14:00 to 15:30

in IM, rear building, ground floor

Let w(F) be the width needed to refute a CNF F in resolution. It is well known that the space needed to refute F in resolution is lower bounded by w(F), and it has been open whether something similar holds for polynomial calculus (PCR).  We show, by a novel 'forcing' argument, that the space needed to refute F in PCR is lower bounded by the square root of w(F). Joint work with Nicola Galesi and Leszek Kolodziejczyk.