Formuła 3-CNF, która wymaga szerokości rozdzielczości

Przypomnijmy, że szerokość o rozdzielczości odrzucenia o wzorze CNF jest maksymalna liczba literałach w klauzuli występującego w . Dla każdego istnieją niezadowalające wzory w 3-CNF st. Każde odrzucenie rozdzielczości wymaga szerokości co najmniej . $R$ $F$ $R$ $w$ $F$ $F$ $w$

Potrzebuję konkretnego przykładu niezadowalającej formuły w 3-CNF (tak małej i prostej, jak to możliwe), która nie ma obalenia rozdzielczości o szerokości 4.

cc.complexity-theory lo.logic sat proof-complexity Jan Johannsen
źródło

Czy potrzebujesz dokładnie szerokości 5 lub co najmniej szerokości 5? W tym drugim przypadku wydaje mi się, że wystarczy kilka losowych klauzul na garstce zmiennych. Jednak niezbyt miły i niezbyt mały.

MassimoLauria,

myślę, że względnie proste wyszukiwanie komputerowe / empiryczne mogłoby to znaleźć lub wykluczyć. myślę też, że czai się tutaj bardziej ogólna / interesująca niezbadana teoria. patrz także w dowodach rozdzielczości, czy wszystkie DAG są możliwe? , szukam ponownego otwarcia głosów, jeśli się zgadzasz =) powiązane pytanie: w przypadku formuł -SAT, jaki wymiar (-y) rozdzielczości DAG są możliwe?

m \times n

$m \times n$

dniu

Jan, myślę, że Jacob powinien być w stanie łatwo odpowiedzieć na to pytanie. Nawiasem mówiąc, czy chciałbyś trochę uogólnić pytanie i zapytać o metodę wymyślenia 3-CNF o danej szerokości rozdzielczości?

Kaveh

Massimo, potrzebuję konkretnego przykładu, który mogę zapisać i wyjaśnić na tablicy. Więc losowe klauzule się nie sprawdzą.

Jan Johannsen,

Znajduję się teraz w niewłaściwej strefie czasowej, aby móc prawidłowo myśleć, ale może zrobiłaby to formuła Tseitin na naprawdę małym wykresie (w którym można sprawdzić ekspansję ręcznie)? Ale naprawdę potrzebujesz 3-CNF, prawda? W przypadku 4-CNF być może bawiłbym się prostokątną siatką o odpowiednich wymiarach i widziałem, co się stanie. Tylko kilka na wpół upieczonych myśli ...

Jakob Nordstrom

Odpowiedzi:

Poniższy przykład pochodzi z pracy, która podaje kombinatoryczną charakterystykę szerokości rozdzielczości przez Atseriasa i Dalmau ( Journal , ECCC , kopia autora ).

Twierdzenie 2 artykułu stwierdza, że biorąc pod uwagę wzór CNF , obalenia rozdzielczości co najwyżej dla są równoważne zwycięskim strategiom dla Spoilera w grze egzystencjalnej . Przypomnijmy, że żwir jest egzystencjalną gra rozgrywa się pomiędzy dwoma konkurującymi podmiotami, zwanych spojler i Powielacz i stanowiska gry są częściowymi przypisania wielkości domeny co najwyżej do zmiennych . W grze -pebble, zaczynając od pustego zadania, Spoiler chce sfałszować klauzulę z , pamiętając co najwyżej $F$ $k$ $F$ $(k+1)$ $k+1$ $F$ $(k+1)$ $F$ $k+1$ wartości logiczne naraz, a Duplicator chce temu zapobiec.

Przykład opiera się na (negacji) szuflady.

Dla każdego i , niech będzie zmienną zdań, co oznacza, że gołąb siedzi w dziurze . Dla każdego i , niech będzie nową zmienną zdań. Poniższy -cnf wzór wyraża to gołębi znajduje się w pewnym otworu: Wreszcie formuła CNN $i \in \{1, \dotsc, n+1 \}$ $j \in \{1, \dotsc, n \}$ $p_{i,j}$ $i$ $j$ $i \in \{1, \dotsc, n+1 \}$ $j \in \{0, \dotsc, n \}$ $y_{i,j}$ $3$ ${EP}_i$ $i$
${E P}_{i} \equiv \neg y_{i, 0} \land ⋀_{j = 1}^{n} (y_{i, j - 1} \lor p_{i, j} \lor \neg y_{i, j}) \land y_{i, n} .$ ${EP}_i \equiv \neg y_{i,0} \wedge \bigwedge_{j=1}^n (y_{i,j-1} \vee p_{i,j} \vee \neg y_{i,j} ) \wedge y_{i,n}.$ $3$ ${EPHP}_n^{n+1}$ ${EP}_i$ $H_k^{i,j} \equiv \neg p_{i,k} \vee \neg p_{j,k}$ $i,j \in \{1, \dotsc, n+1 \}, i \ne j$ $k \in \{1, \dotsc, n \}$

$n$ ${EPHP}_n^{n+1}$ ${EPHP}_n^{n+1}$ $n-1$

Artykuł ma inny przykład w Lemat 9, oparty na zasadzie gęstego rzędu liniowego.

$\Omega(n^{(k-3)/12})$ $k+1$

Siuman
źródło

{E P H P}_{5}^{6}

$\mathrm{EPHP}^6_5$