Abstract

A combinatorial game is defined by a ruleset specifying positions and feasible moves. In the normal-play setting, two players alternate moves, and the player forced to play at a terminal position—where no moves remain—loses. Optimal play often requires deep strategic reasoning and is typically PSPACE-hard. In Combinatorial Game Theory (CGT), the disjunctive sum of two games GGG and HHH, denoted G+HG + HG+H, allows the next player to move in exactly one component game.

In this talk, Prof. Teng shows that the sum of two polynomial-time solvable games can be PSPACE-hard. In other words, P + P ≥ PSPACE, where P and PSPACE represent families of polynomial-time and polynomial-space solvable games, and “+” denotes the disjunctive sum. This contrasts with classical Sprague-Grundy Theory (1930s), which states that the Grundy value of the sum of impartial games can be computed in polynomial time. Assuming PSPACE ≠ P, he proves there is no general polynomial-time method to combine two polynomial-time solvable impartial games to efficiently solve the sum. The results settle two long-standing complexity questions in CGT, open since 1981 and 1993. He will also draw a connection between the theorem and a famous Chinese idiom honouring strategist Zhuge Liang(諸葛亮) from The Romance of the Three Kingdoms(三國演義).