著者
月本 洋
出版者
一般社団法人電子情報通信学会
雑誌
電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)
巻号頁・発行日
vol.103, no.82, pp.29-36, 2003-05-16

本論文ではSATの多項式時間アルゴリズムを提示する。基本的な考えは、以下の通りである。CNFを線形不等式の集合で表現し、値を{O,1}から[0,1]に拡張することで、多面体を得るが、この多面体には充足可能性と関係のない領域が存在する。その領域をある種の線形不等式で切除してゆく。充足不能のときには空になリ、充足可能のときには空にならない。本アルゴリズムは多項式時間アルゴリズムである。よって、P=NPが証明されたことになる。

言及状況

Twitter (3 users, 3 posts, 1 favorites)

なにこれ? 切除平面法じゃね? だれか解説してください. 月本 洋 「SATの多項式時間アルゴリズム (P=NPの証明)」 http://ci.nii.ac.jp/naid/110003178837

収集済み URL リスト