SFI: The Saga of NP-Intermediate Problems …

Eric Allender of Rutgers University
SFI News:
Santa Fe Institute (SFI) present  the seminar, ‘The Saga of NP-Intermediate Problems: A New Devlopment in an Old Story’ at 12:15 p.m. Monday, March 30 in the Collins Conference Room in Santa Fe.
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.
SFI HostCris Moore
Click here to view the online event listing.