acm-header
Sign In

Communications of the ACM

Research highlights

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

Log in to Read the Full Article

Sign In

Sign in using your ACM Web Account username and password to access premium content if you are an ACM member, Communications subscriber or Digital Library subscriber.

Need Access?

Please select one of the options below for access to premium content and features.

Create a Web Account

If you are already an ACM member, Communications subscriber, or Digital Library subscriber, please set up a web account to access premium content on this site.

Join the ACM

Become a member to take full advantage of ACM's outstanding computing information resources, networking opportunities, and other benefits.
  

Subscribe to Communications of the ACM Magazine

Get full access to 50+ years of CACM content and receive the print version of the magazine monthly.

Purchase the Article

Non-members can purchase this article or a copy of the magazine in which it appears.