![Meta-complexity_logo_hi-res](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-02/Meta-complexity_hi-res.png.jpg?itok=oFqprXq1)
Description
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.
All scheduled dates:
Upcoming
No Upcoming activities yet