変数の数に指数関数的に多くの条項がある場合、SATはPにありますか？

Question

私はaを定義します 長いCNF 少なくとも2ドル^ frac {n} {2} $ clausesを含むには、$ n $はその変数の数です。 $ text {long-sat} = { phi： phi $は満足できる長いCNF式$ } $です。

なぜ$ text {long-sat} in p $を知りたいです。最初に、$ text {sat} $から$ text {long-sat} $、no？

しかし、多分私は$ text {2-sat} $を$ text {long-sat} $に減らすことができますか？それ、どうやったら出来るの？

Answer 1

私が何かが足りないのでなければ、それは些細なことです p 式の長さは変数の数で指数関数的であるためです。したがって、すべての$ 2^{n} $真実の割り当てを生成して、式の長さで多項式時間でチェックすることができます。

Answer 2

この場合、答えは些細なことです ルークは指摘します. 。ただし、自分で定義を思いついたように見えるので、これに注意してください。

SATの場合、変数数と節数の比率に関するいわゆる位相遷移が観察されています[1,2]。小さい場合、インスタンスは簡単で、大きい場合は難しいです。簡単なものから硬いものへと多かれ少なかれ鋭い移行があるようです。これはのようです 研究のアクティブな領域. csheory.se この現象にはもう少しあります。

したがって、「長い」の定義を調整すると 多項式 爆発すると、変数よりもはるかに多くの条項があるからといって、実際には簡単ではないクラス、つまりPでは、実際に簡単なクラスを手に入れることができます。

---

1. SAT相遷移 IP Gent（1994）
2. 特徴的な「位相遷移」からの計算の複雑さを決定する R. Monasson、R。Zecchinaet al。 （1999）