第12回セミナー・勉強会
日時: | 2021.06.21 Mon. 10:00-12:00
|
---|---|
会場: | オンライン |
話者: | 玉置 卓(兵庫県立大学,招待講演) |
題目: | SATの解空間連結性判定問題の計算複雑性について |
概要: | SATの解空間連結性判定問題 (CONN-SAT) とは, 論理式の充足解集合により誘導されるハミングキューブの部分グラフが, 連結かどうかを判定する問題である. 充足可能性問題 (SAT) が論理式の種類 (Horn SAT, XOR SAT, 2SAT, 3SAT等) によって計算複雑性が変わるのと同様, CONN-SATの計算複雑性も論理式の種類によって分類できる. 本講演ではCONN-SATの計算複雑性の分類に関する研究を概説する. また, 論理式がk-CNF (CONN-SATがPSPACE完全) の場合に対する指数時間アルゴリズムを紹介する. 本講演は, 牧野和久 氏, 山本真基 氏との共同研究に基づく.
|
2021.06.09 更新