以下の問題3SATはNP完全である。証明の概略を示す。 3SAT INPUT: を変数集合とする。の任意の元か、その否定をリテラル(literal)という。幾つかのリテラルの選言をクローズ(clause)という。であるような幾つかのクローズたちの連言が入力である。 OUTPUT: …
引用をストックしました
引用するにはまずログインしてください
引用をストックできませんでした。再度お試しください
限定公開記事のため引用できません。