Meta-Complexity Seminar

Speaker: Shuichi Hirahara

Title: NP-Hardness of Learning Programs and Partial MCSP



Abstract:

In his seminal paper on the theory of NP-completeness, Levin proved NP-hardness of the partial function version of the Minimum DNF Size Problem in 1973, but delayed his publication because he hoped to prove NP-hardness of Minimum Circuit Size Problem (MCSP). In this talk, I present a proof of NP-hardness of the partial function version of MCSP. The proofs are inspired by NP-hardness of learning programs, the question posed by Ker-I Ko in 1990.   I will mention several open questions that might be within reach.