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.