誰かが O(n^3) 時間で CNF ブール式を与えられたグラフを作成する方法を見つけ、この特別なグラフのスパニング ツリーが CNF 方程式の解になるとします。
このシナリオは、誰かが SAT 問題の解決策を見つけ、O(n^3) 時間で実行されるガジェット (リダクション) を使用して SAT 問題をスパニング ツリー問題に還元することで P=NP を解決したことを暗示しているようです。
しかし、彼らのアルゴリズムが作成するグラフに n があるとしたらどうでしょう! または2 ^ nノードとエッジ？
そのシナリオでは、DFS や BFS などのスパニング ツリー アルゴリズムがノード/エッジの数に対して線形時間で実行される可能性がありますが、ブール式への入力の数に対してポリゴン時間で実行されることはありません。そのため、完全な解を実行するには n! 評価する時間。
この推論は正しいですか？