論理式充足可能性，整数計画，双線形計画

• Item type: SIG Technical Reports(1)
• 公開日: 1993-10-01
• タイトル: 論理式充足可能性，整数計画，双線形計画
• タイトル / 言語: en
• タイトル: Satisfiability, Integer Programming and Bilinear Programming
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京農工大学工学部情報工学大講座
• 著者所属: 東京農工大学工学部情報工学大講座
• 著者所属(英): en
• 著者所属(英): Tokyo University of Agriculture and Technology
• 著者所属(英): en
• 著者所属(英): Tokyo University of Agriculture and Technology
• 著者名: 萩原, 斉; 中森, 眞理雄
• 著者名(英): Hitoshi, Hagiwara; Mario, Nakamori
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 計算量の理論における計算複雑度の定義は，計算機械モデルとその計算機械モデルに対応した記述言語（記述方法）に依存している。本論文では，計算機械モデルを仮定することなく問題の持つ複雑度を表現する記述方法として，各問題を双線形計画問題として記述し，その際に必要となる変数の数を用いて各問題の持つ複雑度を表現する方法を提案する。なお，本論文においては，0?1整数計画問題における可能解の存在性判定問題，論理式の充足可能性問題，ハミルトン閉路の存在性判定問題などを双線形計画問題として記述した結果を示す。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A new measure of problem complexity is proposed. Problems are described as bilinear programming problems and their complexities are evaluated by the number of variables in the bilinear programming form. Unlike the conventional way of evaluating computational complexity, the proposed complexity is independent of models of computation. Problems discussed in the present paper are as follows; determining feasibility of 0-1 integer programming problems, determining satisfiability of logical expressions, finding a Hamilton cycle in a graph, finding a complete subgraph with k vertices, and determining isomorphism of two graphs.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1993, 号 88(1993-AL-035), p. 19-26, 発行日 1993-10-01
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会