Twierdzenie Schaefera i CSP o nieograniczonej szerokości

Twierdzenie dychotomii Schaefera pokazuje, że każdy problem CSP powyżej można rozwiązać w czasie wielomianowym lub jest on NP-kompletny. Dotyczy to tylko problemów CSP o ograniczonej szerokości, z wyłączeniem na przykład SAT i Horn-SAT. Ogólne problemy CSP o nieograniczonej szerokości mogą być bardzo trudne (nawet nieobliczalne), więc ograniczmy się do problemów, które są „naturalne” i dotyczą NP.$\{0,1\}$

Biorąc pod uwagę problem CSP o nieograniczonej szerokości, dla każdego możemy przyjrzeć się ograniczeniu problemu do klauzul o szerokości do . Obowiązuje teraz twierdzenie Schaefera, a ograniczony problem występuje w P lub NP-zupełny. Jeśli z jakiegoś The -restricted problemu jest NP-zupełny, a więc jest nieograniczony problem. Sytuacja jest mniej jasna, gdy dla wszystkich The -restricted problem jest w P.$k$$k$$k$$k$$k$$k$

Twierdzenie o dychotomii Schaefera opiera się na czterech (lub mniej więcej) różnych algorytmach, które rozwiązują wszystkie łatwe przypadki. Załóżmy, że dla danego problemu CSP problem ograniczony przez jest zawsze rozwiązany przez algorytm A. Może się zdarzyć, że algorytm A może być również użyty do rozwiązania problemu nieograniczonego. Albo może być tak, że algorytm A nie jest czasem wielomianowym w przypadku nieograniczonym, a wtedy nie wiemy, jak trudny jest ten problem.$k$

Czy rozważono tego rodzaju problem? Czy istnieją przykłady, w których dochodzimy do miejsca „ignorancji”?

Twierdzę, że dla „naturalnego logicznego CSP”, jeśli wersja z ograniczeniem k jest w P dla każdego k , wówczas wersja nieograniczona jest również w P. Poniżej zdefiniuję „naturalny logiczny CSP”.

Twierdzenie Schaefera stwierdza, że ​​logiczny CSP na skończonym zbiorze S relacji jest w P, jeżeli spełniony jest co najmniej jeden z następujących warunków i jest on NP-kompletny, jeśli żaden z nich nie jest spełniony:

1. Każda relacja w S (z wyjątkiem stałej 0) jest spełniona przez przypisanie 1 do wszystkich jej zmiennych.
2. Każda relacja w S (z wyjątkiem stałej 0) jest spełniona poprzez przypisanie 0 do wszystkich jej zmiennych.
3. Każda relacja w S jest równoważna formule 2-CNF.
4. Każda relacja w S jest równoważna formule klauzuli Horn.
5. Każda relacja w S jest równoważna formule klauzuli podwójnego rogu. („Formuła z podwójnym rogiem” oznacza formułę CNF, w której każda klauzula zawiera co najwyżej jeden literał dodatni.)
6. Każda relacja w S jest równoważna koniunkcji zdań afinicznych.

Załóżmy teraz, że P ≠ NP, i rozważmy przypadek, gdy S jest nieskończone. Jeśli wersja k- ograniczona jest w P dla każdego k , to według twierdzenia Schaefera każdy skończony podzbiór S spełnia co najmniej jeden z sześciu powyższych warunków, a to oznacza, że ​​cały zbiór S spełnia co najmniej jeden z sześciu warunków. Czy to oznacza, że ​​ten CSP bez ograniczeń dotyczących arsenału jest również w P? Jeszcze nie.

Gdy S jest nieskończone, musimy określić, w jaki sposób podawana jest każda klauzula we wzorze wejściowym. Zakładamy, że istnieje jakiś suriekcją mapowanie z {0,1} ^* do S , która określa kodowanie relacji w S . Boolean CSP jest określony przez podanie zarówno S, jak i tej funkcji kodowania.

Zauważ, że w każdym z powyższych przypadków 3, 4, 5 i 6 istnieje naturalny sposób na przedstawienie relacji spełniających warunek: wzór 2-CNF w przypadku 3, wzór z klauzulą ​​Horn w przypadku 4 i tak dalej. Nawet jeśli relacja jest równoważna (powiedzmy) formule 2-CNF, nie ma a priori gwarancji, że jej kodowanie zapewnia łatwy dostęp do formuły 2-CNF, która jest jej równoważna.

Teraz mówimy, że logiczny CSP jest naturalny, gdy jego funkcja kodowania spełnia następujące wymagania:

• Biorąc pod uwagę kodowanie relacji i przypisanie do wszystkich jej zmiennych, to czy relacja jest spełniona czy nie, można obliczyć w czasie wielomianowym. (Uwaga: zapewnia to, że dany CSP jest zawsze w NP.)
• Biorąc pod uwagę kodowanie relacji spełniającej warunek 3, 4, 5 lub 6, jego naturalną reprezentację, jak określono powyżej, można obliczyć w czasie wielomianowym.

Wtedy łatwo zauważyć, że jeśli S spełnia jeden z sześciu powyższych warunków, a kodowanie dla S spełnia ten warunek „naturalności”, wówczas możemy zastosować odpowiedni algorytm. Twierdzenie, które przedstawiłem na początku, można udowodnić, rozważając zarówno przypadek P = NP, jak i przypadek P ≠ NP.