Rozwiązane w czasie wielomianowe wystąpienia Max-Sat

Problem Max-Sat prosi o znalezienie przypisania formuły CNF, która spełnia jak najwięcej klauzul.

Dla prostszego problemu SAT istnieje wiele znanych specjalnych przypadków, które można rozwiązać w czasie wielomianowym, np. Możemy rozwiązać 2-SAT w czasie wielomianowym.

W przypadku Max-Sat sytuacja jest inna, ponieważ Max-Sat jest trudny dla NP nawet dla formuł 2-CNF (każda klauzula zawiera tylko 2 zmienne).

Czy są jakieś ciekawe specjalne dane wejściowe, dla których Max-Sat jest wielomianowy?

W szczególności byłbym zainteresowany standardowym odniesieniem do rozwiązania Max-Sat, gdy wykres impedancji ograniczył szerokość.

To nie odpowiada bezpośrednio na twój problem Max-SAT, ale odniesienia mogą prowadzić cię do pełnej odpowiedzi.

Szeider wykazał, że satysfakcjonowanie jest możliwe do ustalenia, gdy parametr jest sparametryzowany przez szerokość wykresu częstości. Samer i Szeider podali efektywny algorytm programowania dynamicznego.

Bibliografia

S. Szeider. Na parametryzowanych parametrach stałych SAT. W Proc. 6. Międzynarodowa konferencja na temat teorii i zastosowań satysfakcji (SAT'03), Selected and Revised Papers, vol. 2919 LNCS, strony 188–202. Springer-Verlag, 2004.

M. Samer i S. Szeider. Algorytmy zliczania modeli zdań. W Proc. 14. międzynarodowa konferencja nt. Logiki programowania, inteligencji sztucznej i rozumowania (LPAR'07), t. 4790 LNCS, strony 484–498. Springer-Verlag, 2007.

Samer i Szeider, Przyczepność ze stałymi parametrami. W: A. Biere, M. Heule, H. van Maaren i T. Walsh, redaktorzy, Handbook of Satis fi fility, część 1, rozdział 13. IOS Press

Znaleźliśmy jeden rodzaj takiej nieruchomości:

$F$$F$$x$$C$$x$$C$$C$$C$$x$$x$

patrz: http://arxiv.org/abs/1402.6485

Czy są znane jakieś inne takie właściwości?