Ograniczona formuła Monotone 3CNF: liczenie spełniających się zadań (oba modulo

Rozważ formułę Monotone 3CNF mającą oba następujące dodatkowe ograniczenia:

• Każda zmienna występuje dokładnie w klauzulach.$2$
• Biorąc pod uwagę dowolne klauzule, mają one maksymalnie zmienną.$2$$1$

Chciałbym wiedzieć, jak ciężko jest liczyć satysfakcjonujące zadania takiej formuły.

Aktualizacja 06.04.2013 12:55

Chciałbym również wiedzieć, jak trudne jest ustalenie parytetu liczby satysfakcjonujących zadań.

Aktualizacja 11.04.2013 22:40

Co jeśli, oprócz ograniczeń opisanych powyżej, wprowadzimy również oba następujące ograniczenia:

• Formuła jest płaska.
• Formuła jest dwustronna.

Aktualizacja 16.04.2013 23:00

Każde zadowalające przypisanie odpowiada krawędziowej krawędzi regularnego wykresu. Po obszernych poszukiwaniach jedynym istotnym artykułem, jaki udało mi się znaleźć na okładkach do liczenia krawędzi, jest (trzeci) już wspomniany w odpowiedzi Yuvala. Na początku takiego papieru, autorzy mówią „My zainicjować badanie próbek (i związaną z tym kwestię liczenia) wszystkich osłon krawędzi wykresu” . Jestem bardzo zaskoczony, że na ten problem poświęcono tak mało uwagi (w porównaniu z liczeniem pokryw wierzchołków, które jest szeroko badane i znacznie lepiej rozumiane dla kilku klas grafów). Nie wiemy, czy liczenie osłon krawędzi jest . Nie wiemy, czy ustalenie parzystości liczby osłon krawędzi to$3$$\#P$$\oplus P$- twarde też.

Aktualizacja 09.06.2013 07:38

Określanie parzystości liczby osłon krawędzi jest twarde, sprawdź odpowiedź poniżej.$\oplus P$

Na dowolnym wykresie parzystość liczby osłon wierzchołków jest równa parzystości liczby osłon krawędzi.

Aby zobaczyć, dlaczego, sprawdź tę odpowiedź i obserwuj, jak parzystość$|C|$ jest równy parzystości $\Delta_{|V|} = O_{|V|} - E_{|V|}$, który z kolei jest równy parzystości $O_{|V|} + E_{|V|}$, czyli liczba osłon krawędzi.

Obliczanie parzystości liczby osłon wierzchołków wynosi $\oplus$P-twardy: dlatego obliczenie parzystości liczby osłon krawędzi jest $\oplus$P-hard też.

Przynajmniej druga połowa pytania została rozstrzygnięta.

Twój problem jest prawdopodobnie # P-ukończony, chociaż nie udało mi się go znaleźć w literaturze.

Innym sposobem określenia problemu jest „# 3-regular-edge-cover”. Biorąc pod uwagę wzór, skonstruuj wykres, w którym każda klauzula odpowiada wierzchołkowi, a każda zmienna odpowiada krawędzi. Ponieważ formuła jest 3CNF, wykres jest 3-regularny (lub ma maksymalny stopień 3, w zależności od definicji). Ponadto wykres jest prosty. Zadanie zadowalające jest takie samo jak pokrycie krawędzi.

Oto kilka powiązanych problemów:

• # 1-Ex3MonoSat jest # P-kompletny . To jest tak samo jak twój problem, tylko satysfakcjonujące rozwiązanie musi spełniać dokładnie jedną zmienną w każdej klauzuli.
• Zliczanie liczby pokryw wierzchołków na 3-regularnych wykresach płaskich jest # P-ukończone .
• Istnieje FPRAS dla okładki # 3-regular-edge . Sugeruje to, że autorzy uważają, że problem jest trudny.