algorithm - 3 SAT アルゴリズムの複雑さは?

Question

3SAT の興味深いアルゴリズムを実装したいと考えていましたが、同じものをコーディングできなかったため、実際に機能するかどうかを確認できませんでした。このアルゴリズムは、次の Microsoft Word ファイルで定義されています: DropBox Link for 3SAT アルゴリズム このアルゴリズムが実際に機能するかどうか、また機能するかどうかはわかりません。しかし、その複雑さについて本当に知りたいです。これが多項式時間であるかのように、これに関して私を助けてください。そうすれば、P = NPが証明されます!

Answer 1

アルゴリズムの説明にあるように、

このメソッドは、行数が 2 倍になるたびにかなりの時間がかかる場合があります (これは 2 ^mであり、m は節の数です)。

したがって、アルゴリズムの最悪の場合の実行時間は、多項式ではなく指数関数になります。多くの場合、入力の偶然の一致により実行時間が短くなることを期待していますが、最悪の場合の実行時間は、P 対 NP の質問がどのように評価されるかです。