日時：2005年 1月13日（木） 16:00〜17:30 場所：京都大学 本部構内 工学部総合校舎 総合213講義室 講演題目と講演者： ・ 牧野 和久（大阪大学大学院 基礎工学研究科） 「単調論理関数の双対化問題について」講演要旨
単調論理関数の双対化問題について
牧野 和久（大阪大学大学院 基礎工学研究科）
単調な論理関数の双対化問題とは，単調な論理積標準形が与えられ たとき，それと等価な単調な主論理和標準形を求めるという問題で ある． この双対化問題は，数理計画，人工知能，データベース，分散シス テム，学習理論など様々な分野に現れる数多くの重要かつ実用的な 問題と（多項式時間還元の意味で）等価であることが知られている． 現在までのところ，Fredman-Khachiyanによる擬多項式時間アルゴ リズムが知られているが，２０年以上もの間，多項式時間アルゴリ ズムが存在するかどうか未解決のままである． 今回は，この双対 化問題の最近の話題について紹介する．