##### Department of Mathematics,

University of California San Diego

****************************

### Math 268 - Complexity and Logic

## Arnold Beckmann

#### Swansea University

## Parity Games and Resolution

##### Abstract:

Parity games are two player games which are played by moving a token around a finite graph. Parity games have important applications in automata theory, logic, and verification - for example, the model checking problem for the modal mu-calculus is polynomial time equivalent to solving parity games. It is a long-standing open problem whether the winner in a parity game can be decided in polynomial time. In the talk, we will relate this problem to weak automatizability of resolution. A propositional proof system is weakly automatizable if there is a polynomial time algorithm which separates satisfiable formulas from formulas which have a short refutation in the system, with respect to a given length bound. We explain that if the resolution proof system is weakly automatizable, then parity games can be decided in polynomial time. This is joint work with Pavel Pudlak and Neil Thapen.

Host: Sam Buss

### April 16, 2013

### 11:10 AM

### AP&M 6218

****************************