Jakieś wyniki na binarnym CSP typu boolean wykraczają poza ustalalność parametrów prawie problemu 2SAT?

Niech będzie formułą 2CNF, a nieujemną liczbą całkowitą. Jest udowodnione w tym artykule , że problem z podjęciem decyzji, czy można usunąć co najwyżej klauzul aby satisfable określony jest parametr tractable, gdzie jest parametrem. Moje pytanie brzmi: czy są jakieś prace, które uogólniają ten wynik na inne binarne CSP binarne? (To znaczy, aby zdecydować, czy można usunąć co najwyżej ograniczeń, aby niektóre wystąpienia CSP były zadowalające, sparametryzowane przez ) Lub jakieś negatywne wyniki? $\varphi$ $k$ $k$ $\varphi$ $k$ $k$ $k$

parameterized-complexity csp fixed-parameter-tractable

— Prawidłowość
źródło

Naprawdę ciekawi mnie, czego tu brakuje - czy prawie 2SAT nie jest trywialnie dostępny dla stałych parametrów, ponieważ istnieje tylko wielomianowo wiele zestawów co najwyżej klauzul

dla ustalonego

k

$k$

k

$k$

— Dave

@Dave istnieje około

zestawów klauzul, ale ciągliwość parametrów o ustalonych parametrach nie pozwala na pojawienie się

w wykładniczej części środowiska wykonawczego.

O (n^{k})

$O(n^k)$

k

$k$

— Regularność

Według mojej wiedzy ten wariant CSP jest szeroko otwarty. Możesz wyrazić kilka możliwych do rozwiązania problemów o ustalonych parametrach w ustawieniu (np. D-Hitting Set jest mniej więcej przypadkiem, w którym masz dodatnie klauzule wielkości co najwyżej d plus negatywne przypisania; z grubsza oznacza, że problem CSP jest nieco bardziej ogólny, ale łatwo zmniejsza się z powrotem do d-HS lub co najmniej ważonego d-HS). Nawet w przypadku ograniczeń, które można wdrożyć za pomocą formuł 2-CNF istniejących ilościowo, otwarta jest złożoność. Problem polega na tym, że przy implementowaniu ograniczeń w ten sposób, gdy są one 2-CNF, płacisz tylko jeden, aby usunąć całość. Dlatego nawet proste ograniczenia, które są jedynie połączeniem dwóch innych, mogą być trudne (mogę mieć przykład + odniesienie później).

— Stefan Kratsch
źródło