The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content

LAA

Seminar

Resolution by pebbling games

Galesi, N (Rome)
Tuesday 11 April 2006, 16:00-16:30

Seminar Room 1, Newton Institute

Abstract

We present an approach to study the complexity of refutations in Resolution by means of certain pebbling games. We will define certain classes of such games that allow to obtain a new frame for: (1) proving size lower bounds in Resolution; (2) devising new algorithms to find Resolution refutations; (3) characterizing the hardness of provability in Resolution as an "almost" satisfiability. We'll discuss about how to extend a similar approach to stronger systems than Resolution.

Audio

MP3MP3 Real AudioReal Audio

Back to top ∧