式の長さに関する最先端のSATソルバーの時間の複雑さ

Question

DPLLとCDCLのSATソルバーについて学び、それらが変数の数に時間がかかる時間の複雑さを持っていることを知っています。

誤解していない場合、PSがNPに等しくない理由の1つは、数学者やコンピュータの科学者からの途方もない努力にもかかわらず、座っているための多項式 - 時間アルゴリズムが存在しないということです。しかしながら、P対NP問題は、変数の数ではなく、式の長さに関して時間の複雑さについてのみ気にしない。

これらの最先端のSATソルバーが3CNF式で実行された場合、変数の数に対する時間の複雑さ指数関数は、3CNFの長さに対する時間の複雑さ指数関数を意味します。

しかし、それらが任意のCNFで実行された場合、その長さが変数の数に対して指数関数的にすることができる場合、変数の数に対する時間の複雑さ指数関数は必ずしもCNFの長さへの時間の複雑さ指数関数を意味するとは限らない。

このような質問は、時間の複雑さを測定しながら3CNFまたはCNF上で実行されているものですか？

Answer 1

3SATの場合、変数の数は、句の数に多項式的に関連しています。 （正当化のための終わりを参照してください。）

その結果、走行時間が節の数の多項式である3SATのための任意のアルゴリズムも変数の数で多項式であろう。走行時間が変数の数で多項式である3SATのための任意のアルゴリズムも、句の数の多項式であろう。

SAT用の多項式 - 時刻アルゴリズムがある場合に限り、（例えば式のために）多項式の場合に限り、SATのための多項式 - 時間アルゴリズムがある場合に限り、3SATのための多項式 - 時間アルゴリズムがあることが知られている。 。また、SATソルバーに関する何十年もの作業にもかかわらず、多項式の時間（または最悪の場合は指数時間よりも小さい）で実行される3SATのためのすべてのアルゴリズムを認識していません。 3SAT用の多項式-TIMEアルゴリズムがないという証拠としてこれを取ることができます。これは、SATまたはCircuitSatのための多項式 - 時間アルゴリズムがないことを意味し、そのもP！= NP。

---

正当化： $ n $ の数と $ m $ の数を表します。 。 $ n \ le 3m $ （任意の句に表示されない変数は無視され、span class="math-container"> $ m \ LE 8N ^ 3 $ （各節には3つのリテラルがあり、繰り返し句を無視することができます）。その後、 $ n / 3 \ le m \ le 8n ^ 3 $ と $ \ sqrt [3] {m /すなわち、それぞれが他のものと多項式的に関連している。

---

あなたがあなたの質問を修正したことを見ます。それは私があなたが誤解を抱いていると思います。任意のブール式の「SATソルバー」を「走る」[SATソルバー]について話します。ただし、任意のブール式でSATソルバーを実行することはできません。 SATソルバーはCNF式でのみ機能します。

しかし、我々は、一般的な式のサイズのサイズの等しいCNF式に変換できることを知っていますが、その逆も同様です。数式のサイズで時間多項式で任意のブール式の満足性をテストすることができるアルゴリズムがある場合は、式のサイズの時間多項式で3CNF式の満足性をテストすることができるアルゴリズムがあることが続きます（ごく区別3CNF式はブール式であり、したがって、変数の数で時間多項式で3CNF式の満足性をテストすることができるアルゴリズムであり、これは利用可能な証拠に矛盾する。したがって、変数の数の時間多項式で3SATを解くためのアルゴリズムがないと考えている場合は、式のサイズの時間多項式の任意のブール式の充足性をテストするためのアルゴリズムがないと考えてください。< / P>