| 大会名称 |
| 2018年 総合大会 |
| 大会コ－ド |
| 2018G |
| 開催年 |
|
2018
|
| 発行日 |
|
|
| セッション番号 |
|
DS-1
|
| セッション名 |
|
COMP-ELC 学生シンポジウム
|
| 講演日 |
|
2018/3/23
|
| 講演場所(会議室等) |
|
２号館 8Ｆ 2802Ａ教室
|
| 講演番号 |
|
DS-1-8
|
| タイトル |
|
OR-AND-XOR回路に対する回路最小化問題のNP完全性
|
| 著者名 |
|
◎△平原秀一, Oliveira C. Igor, Santhanam Rahul,
|
| キーワード |
|
回路最小化問題, NP完全性
|
| 抄録 |
|
回路最小化問題(Minimum Circuit Size Problem; MCSP)は計算量理論において非常に基礎的で重要な問題である。この問題はNPに属する問題だということは簡単にわかるが、一方でNP完全かどうかについては長い間未解決である。一方で、一般の回路を最小化する代わりに、DNF式を最小化する問題はMasek (1978)によってNP完全であることが示されていた。しかしながら、DNF式よりも表現能力の高い回路クラスに対する回路最小化問題のNP完全性はMasekの結果以来40年間未解決であった。本講演ではその40年来の未解決問題を解決する。具体的には、DNF式(= OR-AND回路)よりも表現能力の高いOR-AND-XOR回路に対する回路最小化問題がNP完全性であることを示す。
|
| 本文pdf |
|
PDF download
|
