Blog
About

104
views
0
recommends
+1 Recommend
1 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Conference Proceedings: found
      Is Open Access

      On the Complexity of Parity Games

      ,

      Visions of Computer Science - BCS International Academic Conference (VOCS)

      BCS International Academic Conference

      22 - 24 September 2008

      Parity games, Total NP search problems, Polynomial Local Search, PLS

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          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 PLS 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.

          Related collections

          Most cited references 7

          • Record: found
          • Abstract: not found
          • Article: not found

          Borel Determinacy

           Donald Martin (1975)
            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Positional strategies for mean payoff games

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              Deciding the winner in parity games is in UP ∩ co-UP

                Bookmark

                Author and article information

                Contributors
                Conference
                September 2008
                September 2008
                : 237-247
                Affiliations
                Department of Computer Science

                Swansea University
                Article
                10.14236/ewic/VOCS2008.20
                © Arnold Beckmann et al. Published by BCS Learning and Development Ltd. Visions of Computer Science - BCS International Academic Conference

                This work is licensed under a Creative Commons Attribution 4.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

                Visions of Computer Science - BCS International Academic Conference
                VOCS
                Imperial College, London, UK
                22 - 24 September 2008
                Electronic Workshops in Computing (eWiC)
                BCS International Academic Conference
                Product
                Product Information: 1477-9358BCS Learning & Development
                Self URI (journal page): https://ewic.bcs.org/
                Categories
                Electronic Workshops in Computing

                Comments

                Comment on this article