Speaker: Shuichi Hirahara
Title: NP-Hardness of Learning Programs and Partial MCSP
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.
All scheduled dates:
No Upcoming activities yet