### arnold beckmann's pages

## On the complexity of parity games

**File:** PDF-File

**Author:** Arnold Beckmann and Faron G Moller

**Title:** On the complexity of parity games

**Proceedings:** Visions of Computer Science
— BCS International Academic Conference

Imperial College, London, UK - 22 - 24 September 2008.
Paper.

**Pages:** 237 - 247

**Abstract:**
Parity games underlie the model checking problem
for the modal μ-calculus, the complexity of which remains
unresolved after more than two decades of intensive research.
The community is split into those who believe this problem
- which is known to be both in `NP` and `coNP` -
has a polynomial-time solution (without the assumption that
`P=NP`) and those who believe that it does not.
(A third, pessimistic, faction believes that the answer
to this question will remain unknown in their lifetime.)

In this paper we explore the possibility of employing
Bounded Arithmetic to resolve this question, motivated
by the fact that problems which are both `NP` and
`coNP`, and where the equivalence between their
`NP` and `coNP` description can be formulated and
proved within a certain fragment of Bounded Arithmetic,
necessarily admit a polynomial-time solution.
While the problem remains unresolved by this paper, we do
proposed another approach, and at the very least provide a
modest refinement to the complexity of parity games (and
in turn the μ-calculus model checking problem):
that they lie in the class of Polynomial Local Search
problems.
This result is based on a new proof of memoryless determinacy
which can be formalised in Bounded Arithmetic.

The approach we propose may offer a route to a polynomial-time
solution. Alternatively, there may be scope in devising a
reduction between the problem and some other problem which is
hard with respect to `PLS`, thus making the discovery of
a polynomial-time solution unlikely according to current
wisdom.