文献

J-GLOBAL ID：201202250037540300   整理番号：12A0787194

変量極小公式の複雑性

著者 (3件)： CHEN Zhenyu (南京大学 計算机軟件新技朮国家重点実験室, 南京) ,  XU Baowen (南京大学 計算机軟件新技朮国家重点実験室, 南京) ,  DING Decheng (南京大学数学系, 南京)
資料名： Kexue Tongbao  (Kexue Tongbao)
巻： 55  号： 12  ページ： 1189-1193  発行年： 2010年 
JST資料番号： C2016A  ISSN： 0023-074X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 中国 (CHN)  言語： 中国語 (ZH)

抄録/ポイント： ロジック公式の極小変量集合の需要に基づき、変量極小等価(VME)の変量極小満足(VMS)問題の理論性質を研究した。等価コア変数と満足可能コア変数の概念を導入することで、判定複雑性のNP-完全とDP-完全を証明した。等価コア変数と満足可能コア変数を通じて、それぞれVMEとVMSを定義した。Unique-SAT VMS VME SATを証明した。その中、Unique-SATが唯一な真値公式類である。VMEがNP-完全であることを証明し、VMSがDPに属す。Data from the ScienceChina, LCAS. Translated by JST

シソーラス用語： *性質 ,  論理 ,  トモグラフィー
準シソーラス用語： *複雑性 ,  ロジック ,  SAT【トモグラフィー】

分類 (1件)： 計算機シミュレーション  (JE11000H)

タイトルに関連する用語 (2件)： 変量 ,  複雑性