Communications of the ACM
Technical Perspective: A Logical Step Toward the Graph Isomorphism Problem
The graph isomorphism problem remains one of those mysteries in theoretical computer science that fascinates laypersons and experts alike. In 1979, Garey and Johnson mentioned the problem in their renowned book on computers and intractability but, in fact, it dates back even earlier and has been unresolved for over half a century. In 2015, a major advance hit the media: Babai's quasipolynomial algorithm. This was the first improvement for the general problem in over 30 years. And yet it remains an open problem. At its core, the problem captures the algorithmic detection of symmetries of combinatorial objects.
Maybe surprisingly, there are various and quite distinct areas in which the problem finds applications. We can find one such application domain in the context of logics. Indeed, the isomorphism problem appears to be closely linked to what logicians call the quest for a logic that captures PTIME, a major open problem in finite model theory. In a nutshell we want a logic that is powerful enough to precisely allow everything that is efficiently solvable to be captured in a formula but is not more powerful than that. In terms of databases, we want a query language expressive enough to allow all queries that can be efficiently answered but again not more than that.
No entries found