Ist SAT in P, wenn es exponentiell viele Klauseln in der Anzahl der Variablen gibt?

Question

Ich definiere a langer CNF mindestens $ 2^ frac {n} {2} $ clausses, wobei $ n $ die Anzahl seiner Variablen ist. Sei $ text {long-sat} = { phi: phi $ ist eine zufriedenbare lange CNF-Formel $ } $.

Ich würde gerne wissen, warum $ text {Long-sat} in p $. Zuerst dachte ich, es ist $ text {npc} $, da ich eine Polynomzeitreduktion von $ text {sat} $ bis $ text {Long-sat} $ durchführen kann, nein?

Aber vielleicht kann ich $ text {2-sa} $ auf $ text {Long-sa} $ reduzieren? Wie mache ich das?

Answer 1

Es sei denn, mir fehlt es etwas, es ist trivial in P Da die Länge der Formel in der Anzahl der Variablen exponentiell ist. Daher können alle $ 2^{n} $ Wahrheitszuweisungen in der Polynomzeit in der Länge der Formel generiert und überprüft werden.

Answer 2

In diesem Fall ist die Antwort trivial als Luke weist darauf hin. Beachten Sie dies jedoch anscheinend die Definition selbst.

Für SAT wurden sogenannte Phasenübergänge bezüglich des Verhältnisses der variablen Anzahl zu Klausel beobachtet [1,2]. Wenn es klein ist, sind Instanzen einfach und hart, wenn es groß ist. Es scheint einen mehr oder weniger scharfen Übergang von leicht zu hart zu geben. Dies scheint ein aktives Forschungsbereich. csthory.se hat noch mehr über dieses Phänomen.

Also, wenn Sie Ihre Definition von "lang" anpassen Polynom Blowup, Sie könnten tatsächlich eine nicht trivial einfache Klasse erhalten-dh in P-, nur weil Sie viel mehr Klauseln als Variablen haben.

---

1. Der SAT -Phasenübergang von IP Gent (1994)
2. Bestimmung der Rechenkomplexität aus charakteristischen "Phasenübergängen" Von R. Monasson, R. Zecchina et al. (1999)