An Improved Subexponential Algorithm for Parity Games

Björklund, HenrikUppsala universitet,Institutionen för informationsteknologi,Datalogi,Computing science (author)

Technical report / Department of Information Technology, Uppsala University,1404-3203 ;2003-017

We suggest a new algorithm for deciding parity games, a fundamental problem of unknown complexity (in NPcapcoNP, not known to belong to P) in game, automata, complexity theories, combinatorial optimization, temporal logic of programs, computer-aided verification. The novelty of the algorithm consists in exploiting a special form of parity games with retreats, where optimal retreat edges define absorbing facets (with better values than their neighbors on complementary facets) in the strategy space. A superset of such absorbing facets can be found by standard random iterative improvement algorithms in expected polynomial time. Additional dual techniques are used to minimize this superset. As a result, the dimension of the problem shrinks, to which we finally apply the Kalai-Matousek-Sharir-Welzl-Ludwig-style randomization techniques we recently adapted for games [Bjorklund, Sandberg, Vorobyov, STACS'2003 and TR-2003-002]

Sandberg, SvenUppsala universitet,Institutionen för informationsteknologi,Datalogi,Computing science(Swepub:uu)svsan813 (author)
Vorobyov, SergeiUppsala universitet,Institutionen för informationsteknologi,Datalogi,Computing science (author)
Uppsala universitetInstitutionen för informationsteknologi (creator_code:org_t)

By the author/editor: Björklund, Henri ...; Sandberg, Sven; Vorobyov, Sergei

About the subject

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.