NP-Hardness of Learning Programs and Partial MCSP
Tuesday, December 6, 2022 - 4:00pm to 5:15pm
Refreshments:
Milk & Cookies served 4--4:15 pm
Location:
32-G449 (Patil/Kiva)
Speaker:
Shuichi Hirahara (National Institute of Informatics, Tokyo, Japan)
Seminar group:
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, we prove NP-hardness of the partial function version of MCSP. Our proofs are inspired by NP-hardness of learning programs, the question posed by Ker-I Ko in 1990.