Ist SAT in P, wenn die Anzahl der Variablen exponentiell viele Klauseln enthält?

7

Ich definiere einen langen CNF , der mindestens enthält $2^\frac{n}{2}$ Klauseln, wobei die Anzahl seiner Variablen ist. Es sei eine erfüllbare lange CNF-Formel . $n$ $\text{Long-SAT}=\{\phi: \phi$ $\}$

Ich würde gerne wissen , warum . Zuerst dachte ich, es sei da ich eine Polynomzeitverkürzung von auf , nein? $\text{Long-SAT} \in P$ $\text{NPC}$ $\text{SAT}$ $\text{Long-SAT}$

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

complexity-theory np-complete reductions satisfiability polynomial-time Zähler
quelle

@Numerator: Pass auf den letzten Satz der Frage auf. Das Reduzieren eines einfachen Problems (in diesem Fall 2-SAT) auf Ihr Problem bedeutet nicht, dass Ihr Problem einfach ist.

Tsuyoshi Ito

1

@ TsuyoshiIto: Wir versuchen, über seltsame Tags auf dem Laufenden zu bleiben. Bitte zögern Sie nicht, das gelegentliche Auftreten zu bearbeiten. Wenn Sie eine weit verbreitete (missbräuchliche) Verwendung feststellen oder auf Widerspruch stoßen, nehmen Sie diese bitte als Meta (anstatt in den Kommentaren unter einer Frage zu diskutieren).

Raphael

12

Sofern mir nichts fehlt, ist es trivial in P, da die Länge der Formel in der Anzahl der Variablen exponentiell ist. Daher alles $2^{n}$ Wahrheitszuweisungen können in Polynomzeit in der Länge der Formel erzeugt und überprüft werden.

Luke Mathieson
quelle

Aber a

2^{n}

$2^n$ Schecks ist immer noch als Plynoimalzeit definiert?

Zähler

4

Denken Sie daran, dass Sie in P einen Algorithmus benötigen, der in Polynomzeit in der Größe der Eingabe ausgeführt wird. In diesem Fall wissen wir das, wenn wir die Größe der Eingabe als N bezeichnen

#clauses \leq N

$\text{#clauses } \leq N$ . Daher haben wir auch

n = O (l o g N)

$n=O(log N)$ so die

2^{n}

$2^n$ Zuweisungen entsprechen nur einem Polynom in der gesamten Eingabegröße

N

$N$ . Lassen Sie sich nicht von Texten täuschen, wenn sie die Variable verwenden

n

$n$ Es ist nur eine Variable, keine spezielle magische Zahl, die immer das beste Maß für die Größe der Eingabe ist. Entschuldigung für die Formatierung, ich tippe dies auf meinem Handy.

Luke Mathieson

@ Zähler: Sie tun

2^{\log n} = n

$2^{\log n}=n$ prüft, wo

n

$n$ ist die Länge der Eingabe.

Xodarap

6

In diesem Fall ist die Antwort trivial, wie Luke betont . Beachten Sie dies jedoch, da Sie die Definition anscheinend selbst erstellt haben.

Für SAT wurden sogenannte Phasenübergänge bezüglich des Verhältnisses von variabler Anzahl zu Klauselanzahl beobachtet [1,2]. Wenn es klein ist, sind Instanzen einfach und schwierig, wenn es groß ist. Es scheint einen mehr oder weniger scharfen Übergang von leicht zu schwer zu geben. Dies scheint ein aktives Forschungsgebiet zu sein . cstheory.SE hat mehr zu diesem Phänomen.

Wenn Sie also Ihre Definition von "lang" an das Polynom- Blowup anpassen, erhalten Sie möglicherweise tatsächlich eine nicht trivial einfache Klasse - das heißt in P -, nur weil Sie viel mehr Klauseln als Variablen haben.

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

Raphael
quelle

4

Tatsächlich ist das Muster bezüglich des Phasenübergangs nicht einfach, sondern einfach. Es gibt zwei Regionen: unter- und überbeschränkt. Im ersten Fall sind die Lösungen dicht verteilt, sodass Sie schnell erfolgreich sind. Im zweiten Fall scheitern Sie schnell: Jeder vernünftige Algorithmus findet eine Lösung, wenn eine solche vorhanden ist (ein starkes Anziehungspunkt), und wenn es keine Lösung gibt, kann ein Backtracking-Algorithmus dies schnell feststellen, da potenzielle Lösungspfade frühzeitig abgeschnitten werden. An der Grenze dieser Regionen liegen schwierige Probleme: Die Wahrscheinlichkeit einer Lösung ist gering, aber nicht zu vernachlässigen.

Juho

Ist SAT in P, wenn die Anzahl der Variablen exponentiell viele Klauseln enthält?

Antworten: