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ść.
Odpowiedzi:
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
źródło
Znaleźliśmy jeden rodzaj takiej nieruchomości:
patrz: http://arxiv.org/abs/1402.6485
Czy są znane jakieś inne takie właściwości?
źródło