Schäfers Theorem und CSPs von unbegrenzter Breite

12

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.kkkkkk

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?

Yuval Filmus
quelle

Antworten:

11

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.

Tsuyoshi Ito
quelle