- 著者
-
月本 洋
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)
- 巻号頁・発行日
- vol.103, no.82, pp.29-36, 2003-05-16
本論文ではSATの多項式時間アルゴリズムを提示する。基本的な考えは、以下の通りである。CNFを線形不等式の集合で表現し、値を{O,1}から[0,1]に拡張することで、多面体を得るが、この多面体には充足可能性と関係のない領域が存在する。その領域をある種の線形不等式で切除してゆく。充足不能のときには空になリ、充足可能のときには空にならない。本アルゴリズムは多項式時間アルゴリズムである。よって、P=NPが証明されたことになる。