What is it about?
Problems in the complexity class NP inter co-NP are thought to be solvable in polynomial time. Because they are in NP, there is an exponential-time algorithm. Until now, for all problems in NP inter co-NP, we have discovered polynomial time algorithms. This works makes the first step towards a polynomial time algorithm for one of these problems. The problem is Turn-based Stochastic Games with discounted objectives. The weights or rewards on states are given as discrete classes, instead of usual numbers. We find a sub-exponential algorithm for this problem.
Featured Image
Photo by Michal Vrba on Unsplash
Why is it important?
Our work connects two separate areas: Number Theory and Theoretical Computer Science. The main technical tool is work done on polynomials and the study of their roots.
Perspectives
I think of this work as the start of a series of publications that leads to the discovery of a polynomial time algorithm for this NP inter co-NP problem.
Raimundo Saona
Institute of Science and Technology Austria
Read the Original
This page is a summary of: Deterministic Sub-exponential Algorithm for Discounted-sum Games with Unary Weights, July 2024, ACM (Association for Computing Machinery),
DOI: 10.1145/3661814.3662080.
You can read the full text:
Contributors
The following have contributed to this page
