Prosty przypadek SAT, który nie jest łatwy do rozpoznania drzewa

10

Czy istnieje naturalna klasa formuł CNF - najlepiej taka, która była wcześniej badana w literaturze - o następujących właściwościach:C

  • jest łatwym przypadkiem SAT, takim jak np. Horn lub 2-CNF, tj. Członkostwo w C można badać w czasie wielomianowym, a wzory F C można badać pod kątem satysfakcji w czasie wielomianowym.CCFC
  • Niezadowalające wzory nie są znane z krótkich (wielkości wielomianowych) odrzuceń przypominających drzewa. Jeszcze lepiej byłoby: istnieją niezadowalające wzory w C, dla których znana jest super-wielomianowa dolna granica rozdzielczości drzewiastej.FCC
  • Z drugiej strony wiadomo , że niezadowalające formuły w mają krótkie proofy w jakimś silniejszym systemie proof, np. W rozdzielczości typu dag lub w jeszcze silniejszym systemie.C

nie powinien być zbyt rzadki, a więc zawierają wiele formuł z n zmiennych dla każdego (lub co najmniej przez większość wartości) n N . Powinien być również nietrywialny w tym sensie, że zawiera zarówno satysfakcjonujące, jak i niezadowalające formuły.CnnN

Znaczenie powinno mieć następujące podejście do rozwiązywania arbitralnej formuły CNF : znajdź częściowe przypisanie α, a resztkowa formuła F α znajduje się w C , a następnie zastosuj algorytm wielomianowy dla formuł w C do F α . Dlatego chciałbym uzyskać inne odpowiedzi oprócz całkowicie odmiennych ograniczeń od obecnie akceptowanej odpowiedzi, ponieważ uważam, że rzadko zdarza się, aby dowolna formuła stała się zupełnie innym ograniczeniem po zastosowaniu ograniczenia.FαFαCCFα

Jan Johannsen
źródło
1
Jan, myślę, że wciąż można podać sztuczne przykłady, np. Związek PHP Horn. Nie jestem pewien, jak formalnie wykluczyć takie przykłady. Czy chcesz mieć klasę, która ma nazwę i była studiowana? (ps: jeśli wyjaśnisz, dlaczego szukasz takiej klasy, która mogłaby pomóc w spełnieniu dodatkowych wymagań, jakie klasa powinna spełnić).
Kaveh
nie jestem pewien co do ostatniego zdania. problemy z szufladami mogą mieć zarówno prawdziwe, jak i fałszywe formuły, prawda? zwykle są to tylko prawdziwe formuły, nie jestem pewien, gdzie są fałszywe formuły w gazecie, czy ktoś jeszcze to widział? naturalną formułą fałszywej szuflady byłaby taka, która próbuje przypisać gołębiom do n dziur. n+1n
vzn
@Kaveh, masz rację, ale prawdopodobnie nigdy nie można wykluczyć sztucznych przykładów. Próbowałem trochę wyjaśnić to pytanie.
Jan Johannsen
Pożądany warunek w ostatniej edycji zasadniczo prosi o dziedziczną klasę. Zauważ, że bezpośrednie kodowanie wszystkich różnych daje dziedziczną klasę instancji SAT. Być może mógłbyś wyjaśnić, dlaczego główny przykład, który mamy (jak sugerują trzy komentarze / odpowiedzi) nie jest odpowiedni?
András Salamon
1
Myślę, że Jan chce naturalnej klasy formuł, a nie rodziny formuł. Trudność jest zarówno „naturalna”, jak i „klasa” to pojęcia nieformalne. Sądzę, że jednym z warunków, które można postawić za bycie klasą, jest wymaganie pewnego poziomu ekspresji lub zamknięcia, aby rodziny formuł takich jak PHP nie były liczone jako klasa. I jeśli chodzi o naturalność, myślę, że jeśli klasa była studiowana wcześniej lub ma nazwę, to prawdopodobnie będzie naturalna.
Kaveh

Odpowiedzi:

10

Wygląda na to, że interesują Cię różne ograniczenia (a twoje ostatnie zdanie jest na dobrej drodze). Są to nietrywialne przypadki zasady szufladki, w których liczba gołębi niekoniecznie jest większa niż liczba dziur, a ponadto niektóre gołębie mogą zostać wykluczone z niektórych dziur.

Różnorodne ograniczenia można ustalić, dopasowując w czasie wielomianowym niskiego rzędu.

Kiedy wyrażane są różne ograniczenia (przy użyciu jednego z kilku kodowań) jako instancje SAT, wówczas uczenie się klauzul opartych na konflikcie zwykle szybko znajduje rozwiązanie, jeśli takie istnieje. Jednak czysta rozdzielczość dla PHP musi zbudować superpolinomalnie duży zestaw klauzul, aby pokazać, że instancja jest niezadowalająca. Ta granica wyraźnie dotyczy tego bardziej ogólnego problemu. Z drugiej strony, pamiętaj, że kodowanie Cooka w PHP pozwala na odrzucenie wielomianowej rozszerzonej rozdzielczości.

  • SA Cook, Krótki dowód na zasadę gołębia przy użyciu rozszerzonej rozdzielczości , SIGACT News 8 28–32, 1976. doi: 10.1145 / 1008335.1008338

Ostatnie prace w tym kierunku to Rozdział 5 pracy Sergi Oliva , który stanowił podstawę artykułu z Alberto Atseriasem na CCC 2013.

Oczekuję, że znasz klasyczny wynik Cooka, więc może chciałeś ograniczyć moc systemu dowodowego w trzecim stanie?

András Salamon
źródło
Nie jestem pewien, czy tego właśnie szuka Jan, pytając konkretnie o CNF.
Mikolas
@Mikolas: czy możesz wyjaśnić, czym się martwisz?
András Salamon
1
Miałem na myśli, że jeśli mam jakiś wynik na temat różnych ograniczeń, to nie jest jasne, jak ten wynik przekłada się na CNF. Jak rozumiem pytania, Jan chciał CNF twardych na resory drzewne, ale łatwych na coś innego (np. Dag-res). Nie jest dla mnie jasne również, dlaczego PHP byłby tego przykładem, ponieważ PHP ma również charakter wykładniczy dla dag-res. (BTW, przywołana teza wygląda na
porządną
@mikolas jak rozumiem pytanie, czy zadowalające / niezadowalające przypadki rodziny można rozpoznać w czasie P, ale trudno jest rozstrzygnąć drzewo lub DAG, to jest to, czego się szuka. teraz nie jestem pewien, czy zostało to wskazane w jakichkolwiek artykułach, ale afaik (ktoś wie więcej?), instancje sat / unsat PHP można rozpoznać w czasie P.
vzn
1

Nie jestem pewien, dlaczego wymagałoby to również formuł sat, ale jest kilka artykułów na temat rozdzielenia rozdzielczości ogólnej od drzewa, np. [1]. Wydaje mi się, że tego właśnie chcesz.

[1] Ben-Sasson, Eli, Russell Impagliazzo i Avi Wigderson. „Niemal optymalne rozdzielenie rozdzielczości drzewiastej i ogólnej.” Combinatorica 24.4 (2004): 585–603.

Mikolas
źródło
1
Doskonale zdaję sobie sprawę z tych podziałów między rozdzielczością przypominającą drzewo i dag, ale daje to tylko jedną rodzinę formuł. To jest właśnie ten sztuczny przykład, którego starałem się uniknąć.
Jan Johannsen
0

Możesz być zainteresowany formułami SAT z małą (logarytmiczną) „przepustowością” lub „treewidth”. Te formuły są rekurencyjnie partycjonowane w taki sposób, że granica komunikacji między partycjami jest niewielka, a zatem do ich rozwiązania można zastosować numeryczne podejście do programowania dynamicznego. Temat był popularny w latach dziewięćdziesiątych. Kiedyś policzyłem dokładnie liczbę cykli hamiltonowskich na małym wykresie szerokości 24 000 wierzchołków, więc problemy #P przy małej szerokości są również do rozwiązania. Bodlaender jest ważnym punktem odniesienia.

Daniel Pehoushek
źródło
Myślę, że przynajmniej formuły o stałej szerokości drzewa obalają krótkie drzewiaste rozdzielczości. Nie sądzę więc, aby ta klasa spełniała wymagania pytania.
Jan Johannsen
-1

ten następujący artykuł wydaje się zbliżony do tego, co jest wymagane w pewien sposób (jeśli nie pasuje, być może JJ może wyjaśnić, dlaczego). pytanie chce wykluczyć instancje PHP (szufladki) na podstawie braku obu formuł prawda / fałsz, ale (jak cytowano w innych odpowiedziach) PHP jest jednym z najlepiej zbadanych przypadków / generatorów instancji od strony teorii i ma zawsze był generatorem zarówno satysfakcjonujących / niezadowalających formuł, chociaż satysfakcjonujące formuły są mniej podkreślane / badane.

nmmnm>nmn

innym podejściem byłoby pójście pod bardziej empirycznym kątem i po prostu generowanie losowych instancji (prawdopodobnie wokół łatwego, trudnego, łatwego do osiągnięcia w 50% punktu przejścia) i filtrowanie ich w celu spełnienia podanych kryteriów. wymagałoby to implementacji rozdzielczości drzewa / rozdzielczości DAG lub „silniejszych systemów”.

vzn
źródło
1
Obowiązuje ten sam komentarz, co w odpowiedzi @Mikolas.
Jan Johannsen
1
nie rozumiem twojego komentarza, potrzebujesz więcej informacji. śledzę komentarz Mikolasa „Jak rozumiem pytania, Jan chciał CNF twardych dla res-tree, ale łatwych dla czegoś innego (np. dag-res).” co rozumiesz przez „daje to tylko jedną rodzinę formuł”? twoje pytanie dotyczy rodziny formuł.
vzn
1
Nie, moje pytanie dotyczy klasy formuł. Różnica polega na tym, że te rodziny formuł mają co najwyżej jedną formułę na liczbę zmiennych, podczas gdy odpowiednia klasa powinna mieć wiele formuł na każdą liczbę zmiennych, wśród tych satysfakcjonujących i niezadowalających.
Jan Johannsen
Wyjaśniłem już w kilku miejscach (por. Komentarz tutaj i inne odpowiedzi oraz pytanie), dlaczego nie tego szukam !! W szczególności przeczytaj ostatni akapit pytania!
Jan Johannsen