29 September 2021 – Professors Sanjay Jain and Frank Stephan and their research collaborators, lecturer Wei Li from the NUS Department of Mathematics, Professors Cristian Calude from the University of Auckland, and Bakhadyr Khoussainov from the University of Electronic Science and Technology of China and the University of Auckland, have won the EATCS-IPEC Nerode Prize for their paper on Deciding Parity Games in Quasipolynomial Time.
The prize was presented at the virtual International Symposium on Parameterized and Exact Computation (IPEC) in September this year. It is awarded to outstanding papers in the area of multivariate algorithmics, and is named in honor of Anil Nerode in recognition of his major contributions to mathematical logic, theory of automata, computability and complexity theory.
IPEC was held as part of ALGO 2021, which is an annual meeting combining a premier algorithmic conference, the European Symposium on Algorithms, and a number of other specialised conferences and workshops related to algorithms.
The paper for which the team received the prize explored how parity games can be solved in quasipolynomial time. The paper detailed a rough exponential improvement in the running time of verified algorithms.
“The quasipolynomial time algorithm improved the best-known verified runtime of parity games from n^(constant*Sqrt(n)) to n^(log(n)+constant). While the first type of function is still within the range of the known complexity of typical NP-complete problems, the second one is definitely better and is quite near to polynomial time,” explained Prof Stephan on behalf of his research collaborators.
NP-complete problems are a class of hardest problems in the class of problems which can be non-deterministically solved in polynomial time. There are no known efficient (polynomial time) solutions for these problems.
“This big jump in the complexity made the paper stand out. The ideas turned out to be quite natural and once the result and its method were known, researchers discovered that many known algorithms for parity games can be tweaked such that they run in quasipolynomial time,” added Prof Stephan.
The exact time complexity solving parity games is a long-standing open question in theoretical computer science. Prof Khoussainov discussed this problem with many colleagues, including those in Auckland and Singapore, and tried to solve the problem jointly with many collaborators for many years.
“When trying to make parity games into P, it was tempting to look at alternating computations, as games have this alternation inherently in their model. However, these computation must work with logspace memory and therefore all our attempts to do this failed,” Prof Stephan said.
Added Prof Stephan: “When revisiting the problem in 2016, we looked at the known complexity bounds more carefully and noticed that allowing slightly more than log space in the alternating model still gives a good result.”
Prof Stephan and his collaborators also strove for improvements and results in their research, not perfection.
“As a German proverb says, ‘the perfect is the enemy of the good’. Instead of searching for the perfect solution, in this case a polynomial time algorithm, one has sometimes to settle for the ‘good result’ – the quasipolynomial time – and that then worked,” Prof Stephan said.
While Prof Khoussainov believes that there is a polynomial time algorithm for parity games, Prof Calude and Prof Stephan think that the quasipolynomial time complexity cannot be improved; however, a proof for this would solve the P-NP problem (to the classes being different), and is therefore, very difficult to obtain.
