問題タブ [2-satisfiability]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
18 問題
0
投票する
1
に答える
50
参照
cryptography - 定数入力は、問題の SAT 定式化にどのように影響しますか?
N 個の入力と 1 個の出力を持つブラック ボックス回路があるとします。
M 入力の値を修正し、回路が満足できる残りの入力 (NM) の値を見つけたいと考えています。Verilog RTL の M 入力を手動で修正し、(abc を使用して) CNF に変換すると、正しい結果が得られますか? この種の問題に対する正しいアプローチですか？
0
投票する
1
に答える
320
参照
algorithm - 2 SAT を多項式時間で解いて、強連結成分を見つけることができることを理解しています。同じことを 3SAT で行うのはどうですか?
3SAT の場合、1 つの句に対して 2 つの含意を得る代わりに、おそらく 12(3C2*2*2) が得られます。これは、m が 3 つの CNF の句の数である場合、12m のエッジのグラフを形成します。その結果のグラフで強連結成分を見つけます。3 SAT を P 問題にするこのステートメントのどこが間違っていますか? 例えば。