We care about your data, and we'd like to use cookies to give you a smooth browsing experience. Please agree and read more about our privacy policy.
Quanta Homepage
  • Physics
  • Mathematics
  • Biology
  • Computer Science
  • Topics
  • Archive
Complexity Theory Problem Strikes Back
Comment
Read Later
Share
Facebook
Twitter
Copied!
Copy link
Email
Pocket
Reddit
Ycombinator
Flipboard
    • Comment
      Comments
    • Read Later
    By Erica Klarreich

    Contributing Correspondent


    January 5, 2017


    View PDF/Print Mode
    Abstractions blogalgorithmscomputational complexitycomputer sciencegraph theorymathematicspolynomialsAll topics
    Abstractions blog

    Complexity Theory Problem Strikes Back

    By Erica Klarreich

    January 5, 2017

    The legendary graph isomorphism problem may be harder than a 2015 result seemed to suggest.
    Comment
    Read Later

    Introduction

    The theoretical computer scientist László Babai has retracted a claim that amazed the computer science community when he made it just over a year ago. In November 2015, he announced that he had come up with a “quasi-polynomial” algorithm for graph isomorphism, one of the most famous problems in theoretical computer science. While Babai’s result has not collapsed completely — computer scientists still consider it a breakthrough — its central claim has been found, after a year of close scrutiny, to contain a subtle error. (January 9, 2017, update: Babai announced that he has fixed the error and renewed his claim that his algorithm runs in quasi-polynomial time, adding that he is “working on an updated arXiv posting.”)

    “In Laci Babai, you have one of the most legendary and fearsome theoretical computer scientists there ever was, and in graph isomorphism, one of the most legendary and fearsome problems,” wrote Scott Aaronson, a theoretical computer scientist at the University of Texas, Austin, in an email. “A year ago, Laci threw an unbelievable knockout punch at [graph isomorphism], and now the problem itself seems to have gotten off the mat and thrown a counterpunch.”

    The graph isomorphism problem asks for an algorithm that can spot whether two graphs — networks of nodes and edges — are the same graph in disguise. For decades, this problem has occupied a special status in computer science as one of just a few naturally occurring problems whose difficulty level is hard to pin down.

    Roughly speaking, most computer science problems fall into one of two broad categories. There are “easy” problems, the ones that can be solved in a polynomial number of steps — if the size of the problem is denoted by n, the number of steps grows as, for example, n2 or n3. These problems can (generally) be solved efficiently on a computer. And there are “hard” problems, for which the best known algorithm takes an exponential (such as 2n ) number of steps — far too many for a computer to carry out efficiently. Only a handful of natural problems, including graph isomorphism, seem to defy this dichotomy; computer scientists have struggled for decades to figure out just where graph isomorphism belongs.

    Babai, a professor at the University of Chicago, had presented in late 2015 what he said was a “quasi-polynomial” algorithm for graph isomorphism. His work appeared to place the problem, if not firmly in the easy zone, then at least in its suburbs. But on January 4 he announced that while his algorithm still works (with some small tweaks) and has now been carefully checked by other computer scientists, it doesn’t run as fast as he had thought. It is “sub-exponential,” which moves the problem back into the suburbs of the hard zone.

    Babai’s algorithm is, nevertheless, significantly faster than the previous best algorithm for graph isomorphism, which had held its title unchallenged for more than 30 years. “It’s still a massive improvement over the previous state of the art,” said Aaronson by email. Computer scientists conversant in Babai’s approach will presumably try to figure out whether further improvements can be milked from it, Aaronson predicted.

    In a statement on his University of Chicago web page, Babai thanked Harald Helfgott, a mathematician at the University of Göttingen and France’s National Center for Scientific Research, for “spotting this error and for spending months studying the paper in full detail.” Helfgott, in a blog post, wrote that despite the error in Babai’s work, the remainder of his paper is “rich in innovative ideas.”

    To learn more about the graph isomorphism problem, read Erica Klarreich’s 2015 article “Landmark Algorithm Breaks 30-Year Impasse.”

    Share this article
    Facebook
    Twitter
    Copied!
    Copy link
    Email
    Pocket
    Reddit
    Ycombinator
    Flipboard

    Newsletter

    Get Quanta Magazine delivered to your inbox

    Recent newsletters
    By Erica Klarreich

    Contributing Correspondent


    January 5, 2017


    View PDF/Print Mode
    Abstractions blogalgorithmscomputational complexitycomputer sciencegraph theorymathematicspolynomialsAll topics
    Share this article
    Facebook
    Twitter
    Copied!
    Copy link
    Email
    Pocket
    Reddit
    Ycombinator
    Flipboard

    Newsletter

    Get Quanta Magazine delivered to your inbox

    Recent newsletters
    The Quanta Newsletter

    Get highlights of the most important news delivered to your email inbox

    Recent newsletters

    Comment on this article

    Quanta Magazine moderates comments to facilitate an informed, substantive, civil conversation. Abusive, profane, self-promotional, misleading, incoherent or off-topic comments will be rejected. Moderators are staffed during regular business hours (New York time) and can only accept comments written in English. 

    Marcus Feldman in his office at Stanford University, CA

    Next article

    Finding the Actions That Alter Evolution
    Quanta Homepage
    Facebook
    Twitter
    Youtube
    Instagram

    • About Quanta
    • Archive
    • Contact Us
    • Terms & Conditions
    • Privacy Policy
    • Simons Foundation
    All Rights Reserved © 2023