Sökning: id:"swepub:oai:DiVA.org:uu-49006" >
An Improved Subexpo...
An Improved Subexponential Algorithm for Parity Games
-
- Björklund, Henrik (författare)
- Uppsala universitet,Institutionen för informationsteknologi,Datalogi,Computing science
-
- Sandberg, Sven (författare)
- Uppsala universitet,Institutionen för informationsteknologi,Datalogi,Computing science
-
- Vorobyov, Sergei (författare)
- Uppsala universitet,Institutionen för informationsteknologi,Datalogi,Computing science
-
(creator_code:org_t)
- Uppsala: Department of Information Technology, Uppsala University, 2003
- Engelska.
-
Serie: Technical report / Department of Information Technology, Uppsala University, 1404-3203 ; 2003-017
- Relaterad länk:
-
https://uu.diva-port... (primary) (Raw object)
-
visa fler...
-
https://urn.kb.se/re...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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]
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences (hsv//eng)
Publikations- och innehållstyp
- vet (ämneskategori)
- rap (ämneskategori)