Reduction from OV to Generalized Büchi Games
Revision as of 12:19, 15 February 2023 by Admin (talk | contribs) (Created page with "FROM: OV TO: Generalized Büchi Games == Description == == Implications == assume: OVH<br/>then: there is no $O(m^{2-\epsilon})$ or $O(\min_{1 \leq i \leq k} b_i \cdot (k \cdot m)^{1-\epsilon})$-time algorithm (for any $\epsilon > {0}$ for generalized Büchi games. In particular there is no such algorithm for deciding whether the winning set is non-empty or deciding whether a specifc vertex is in the winning set. == Year == 2016 == Reference == Chat...")
FROM: OV TO: Generalized Büchi Games
Description
Implications
assume: OVH
then: there is no $O(m^{2-\epsilon})$ or $O(\min_{1 \leq i \leq k} b_i \cdot (k \cdot m)^{1-\epsilon})$-time algorithm (for any $\epsilon > {0}$ for generalized Büchi games. In particular there is no such algorithm for deciding whether the winning set is non-empty or deciding whether a specifc vertex is in the winning set.
Year
2016
Reference
Chatterjee, K., Dvořák, W., Henzinger, M., & Loitzenbauer, V. (2016). Conditionally Optimal Algorithms for Generalized B\" uchi Games. arXiv preprint arXiv:1607.05850.