Schäfers Theorem und CSPs von unbegrenzter Breite

Schaefers Dichotomiesatz zeigt, dass jedes CSP-Problem über entweder in Polynomialzeit lösbar oder NP-vollständig ist. Dies gilt nur für CSP-Probleme mit begrenzter Breite, beispielsweise ohne SAT und Horn-SAT. Allgemeine CSP-Probleme mit unbegrenzter Breite können sehr schwierig (sogar nicht berechenbar) sein. Beschränken wir uns daher auf Probleme, die "natürlich" sind und sich in NP befinden.$\{0,1\}$

Bei einem CSP-Problem mit unbegrenzter Breite können wir uns für jedes die Einschränkung des Problems auf Klauseln mit einer Breite von bis zu k ansehen . Es gilt nun der Satz von Schaefer, und das eingeschränkte Problem ist entweder in P oder NP-vollständig. Wenn für einige k das k- eingeschränkte Problem NP-vollständig ist, ist dies auch das uneingeschränkte Problem. Die Situation ist weniger klar, wenn für alle k das k- eingeschränkte Problem in P ist.$k$$k$$k$$k$$k$$k$

Schaefers Dichotomiesatz basiert auf vier (oder so) verschiedenen Algorithmen, die alle einfachen Fälle lösen. Angenommen, für ein gegebenes CSP-Problem ist das eingeschränkte Problem immer durch den Algorithmus A lösbar. Es könnte der Fall sein, dass der Algorithmus A auch zum Lösen des uneingeschränkten Problems verwendet werden kann. Oder es könnte sein, dass Algorithmus A im uneingeschränkten Fall keine Polynomzeit ist, und wir wissen dann nichts über die Härte des Problems.$k$

Wurde dieses Problem in Betracht gezogen? Gibt es Beispiele, bei denen wir am "unwissenden" Ort ankommen?

Ich behaupte, dass für einen "natürlichen Booleschen CSP", wenn die k- eingeschränkte Version in P für jeden ist k , die uneingeschränkte Version auch in P ist. Ich werde unten ein "natürliches Boolesches CSP" definieren.

Der Satz von Schaefer besagt, dass der Boolesche CSP auf einer endlichen Menge S von Beziehungen in P ist, wenn mindestens eine der folgenden Bedingungen erfüllt ist, und dass er NP-vollständig ist, wenn keine von ihnen erfüllt ist:

1. Jede Beziehung in S (mit Ausnahme der Konstanten 0) wird erfüllt, indem allen Variablen 1 zugewiesen wird.
2. Jede Beziehung in S (mit Ausnahme der Konstanten 0) wird erfüllt, indem allen Variablen 0 zugewiesen wird.
3. Jede Beziehung in S entspricht einer 2-CNF-Formel.
4. Jede Relation in S entspricht einer Horn-Klausel-Formel.
5. Jede Relation in S entspricht einer Dual-Horn-Klausel-Formel. (Eine "Dual-Horn-Klausel-Formel" bezeichnet eine CNF-Formel, bei der jede Klausel höchstens ein positives Literal enthält.)
6. Jede Relation in S ist gleichbedeutend mit einer Konjunktion affiner Klauseln.

Nehmen wir nun an, dass P ≠ NP ist, und betrachten Sie den Fall, in dem S unendlich ist. Wenn die k- eingeschränkte Version für jedes k in P ist , dann erfüllt nach Schaefers Theorem jede endliche Teilmenge von S mindestens eine der sechs obigen Bedingungen, und dies bedeutet, dass die gesamte Menge S mindestens eine der sechs Bedingungen erfüllt. Bedeutet dies, dass dieser CSP ohne Einschränkung der Arität auch in P ist? Noch nicht.

Wenn S unendlich ist, müssen wir angeben, wie jede Klausel in der Eingabeformel angegeben wird. Wir nehmen an, dass es eine surjektive Zuordnung von {0,1} ^* zu S gibt , die die Kodierung der Beziehungen in S angibt . Ein Boolescher CSP wird angegeben, indem sowohl S als auch diese Codierungsfunktion angegeben werden.

Beachten Sie, dass es in jedem der obigen Fälle 3, 4, 5 und 6 eine natürliche Möglichkeit gibt, Beziehungen darzustellen, die die Bedingung erfüllen: eine 2-CNF-Formel in Fall 3, eine Horn-Klausel-Formel in Fall 4 und so weiter. Selbst wenn eine Relation einer 2-CNF-Formel entspricht, gibt es keine A-priori-Garantie dafür, dass ihre Kodierung einen einfachen Zugriff auf die 2-CNF-Formel ermöglicht, die dieser Formel entspricht.

Nun sagen wir, dass ein boolescher CSP natürlich ist, wenn seine Codierungsfunktion Folgendes erfüllt:

• Wenn eine Relation codiert und allen Variablen zugewiesen wird, kann in Polynomzeit berechnet werden, ob die Relation erfüllt ist oder nicht. (Hinweis: Dadurch wird sichergestellt, dass sich der betreffende CSP immer in NP befindet.)
• Bei gegebener Codierung einer Beziehung, die die Bedingung 3, 4, 5 oder 6 erfüllt, kann ihre natürliche Darstellung, wie oben angegeben, in Polynomzeit berechnet werden.

Dann ist es leicht zu erkennen, dass wir den entsprechenden Algorithmus anwenden können , wenn S eine der sechs obigen Bedingungen erfüllt und die Kodierung für S diese „Natürlichkeitsbedingung“ erfüllt. Die Behauptung, die ich eingangs aufgestellt habe, lässt sich beweisen, indem man sowohl den Fall von P = NP als auch den Fall von P ≠ NP betrachtet.