NP困難に対するアプローチとして以下の3つがある 指数時間の最悪計算量の低減 局所探索 線形計画法への緩和 基本:指数部の計算量を改善すれば困難問題が解ける 現在一般的な戦略がない 以下, 質疑応答 柳沼: 1.84はどこから 若林: 帰納法で証明される 笠原: 実行可能解とは 若林: 解のこと. 変数の組. 柳沼: ポリトープと超平面の違いは 若林: 多面体の表面がポリトープ, 中身が実行可能解    制約条件によって出来る多面体の面がポリトープ 柳沼: 探索は 若林: 面に沿って行う 森部: 充足可能性問題が指数計算とは 若林: 例として, 変数5つ. 2の5乗    今回の例なら1.84のn乗 柳沼: 1.84なら4,000倍の計算速度 日下部: 3SATで消していく理由 若林: p.3の定義による. 若林: 深さ可変は役に立ちそう    局所解から脱することが出来る 今泉: プライマルデュアルスキーム, 双対を利用する意味は 若林: 上界を求めるところがキモ    ある解に対して主問題, 双対問題双方から解を挟む 今泉: p.24, 最適解が一致するのは正しいのか 若林: 最適解は一致する 柳沼: 双対問題は基本的に一致する    緩和して反対を解いてる    制約式が減る 浦田: デュアルとかLとか, 良さが伝わらない    概念的には正しいが, 双対問題は式形が変わるから解ける 柳沼: デュアルは制約が増える場合もある 笠原: 指数時間の最悪計算量を減らしたい 若林: 一般的な計算量削減方法がない    指数計算量を減らすのが大目標 笠原: 近似解を求めているのか 若林: 厳密解を求めている, 計算量を減らす工夫をしている