Strategy Logic is a formal language used in computer science and logic to reason about strategic behavior in multi-player games. It lets you write precise statements like "there exists a strategy for player A such that, no matter what player B does, some goal is achieved." Because it can quantify over strategies and mix these quantifiers in complex ways, it is considerably more expressive than older logics used for the same purpose. A central practical question is satisfiability: given a formula in this logic, is there any game-like structure where the formula holds true?
The paper pins down exactly how hard this satisfiability problem is. The answer is that it sits at the very top of a well-known hierarchy of mathematical difficulty, being equivalent in complexity to the entire theory of second-order arithmetic. This is an extraordinarily high level of undecidability, far beyond simply being undecidable in the ordinary sense. Crucially, the authors show this hardness already appears in a very simple-looking fragment of the logic, one that only talks about what happens at the very next moment in time and uses only basic Boolean goals. This means the intractability is not an artifact of exotic features but is baked into the logic's core design.
The practical consequence is stark: Strategy Logic cannot be given any complete proof system, even if you allow infinitely long but computably described proofs (so-called omega-rules). There is no algorithmic procedure, however indirect, that could in principle enumerate all and only the valid formulas. For researchers building verification tools or studying multi-agent systems, this result sets a firm theoretical ceiling, suggesting that any useful application of Strategy Logic will require working with carefully restricted fragments rather than the full language.