2

計算複雑性理論では、すべての整数nについて、入力サイズnの問題を解く計算の数がcf(n)によって制限される場合、アルゴリズムの複雑性はO(f(n))であると言います。ここで、cは a です。nに依存しない正の定数、およびf(n)はnと同様に無限大になる増加関数です。

3-SAT問題は次のように述べられています:句に正確に 3 つのリテラルがある CNF 式が与えられた場合、式全体を真にする変数への TRUE 値と FALSE 値の割り当てはありますか?

CNF 式は、たとえば、m個の変数x1, ..., xmを含むk 個の句で構成されます。 3-SAT に多項式の複雑さP(n)があるかどうかを判断するには、問題の「 nとは何か」という単純なことを理解する必要があります。

私の質問は：

この特定の 3-SAT問題では、入力サイズnはどれと見なされますか?

節の数kですか？それとも変数の数mですか？
またはnはkとmの関数ですか? ( n=f(k,m) )。

この単純な問題で困っています。

Timmie Smith の回答によると、見積もりを考慮することができます。

k <= constant * f(m)

ここで、mはmの多項式関数です。
より正確には、関数P(m)は指数3 (つまり、3 次) と見なすことができます。

したがって、3-SAT の複雑さf(k)を考慮すると、次のようになります。

f(k, m)=f(P(m),m), (with P(m) = m^3).

したがって、関数fがkとmで多項式の場合、実際にはmで多項式になります。したがって、mを入力サイズと見なすことにより、3-SAT が P に含まれているかどうかを知るために 、特定のアルゴリズムがmで多項式であるかどうかを推定することになります。

あなたが同意するなら、私はティミーの答えを良いものとして受け入れることができます.

アップデート：

ここで同じ質問をしました：

https://cstheory.stackexchange.com/questions/18756/whats-the-meaning-of-input-size-for-3-sat

受け入れられた答えは私にとって役に立ちました。

4

3 に答える 3

3

入力サイズは変数の数ですm。

この理由は、問題を解決するためにトラバースする必要がある探索空間のサイズが、変数の数によって完全に決定されるためです。各変数には 2 つの可能な状態 (1 または 0) があり、探索空間は可能なすべての割り当てで構成されます。 . ブルート フォース アルゴリズムは、すべての可能な割り当て ( 2^m) をテストして、検索スペースをトラバースします。ほとんどの 3-SAT アルゴリズムは、節の数によって大きな影響を受けますが、根本的な問題の複雑さには影響しません。

したがって、入力サイズは単純な古い SAT の変数の数でもあり、探索空間は同じように見えますが、力ずくではない方法で節を解決する方法はまったく異なります。

于 2013-08-26T08:00:20.710 に答える