Graph theory

From InterSciWiki
Jump to: navigation, search


Minimum Circuit Size Problem and Graph Isomorphism solved

The Saga of NP-Intermediate Problems: A New Development in an Old Story Eric Allender


Eric Allender

Rutgers University

Abstract: For roughly four decades, two of the best-studied problems in NP that are not known to be in P or to be NP complete have been:

  • Graph Isomorphism, and
  • MCSP (the Minimum Circuit Size Problem).

Yet there had been no theorem, relating the complexity of these two problems to each other.

Until now. We give a simple argument — drawing on the connection between MCSP and time-bounded Kolmogorov complexity — showing that not only Graph Isomorphism, but every problem in the complexity class SZK (Statistical Zero Knowledge) is BPP reducible to MCSP.

Joint work with Bireswar Das: http://ftp.cs.rutgers.edu/pub/allender/szk.mcsp.pdf.

SFI Host: Cris Moore

Click here to view the online event listing.

The Santa Fe Institute is a nonprofit research center located in Santa Fe, New Mexico. Its scientists collaborate across disciplines to understand the complex systems that underlie critical questions for science and humanity. The Institute is supported by philanthropic individuals and foundations, forward-thinking partner companies, and government science agencies.