Looking for a version of Schaefer's dichotomy theorem when each variable occurs at most twice

G Istrate - 1997 - urresearch.rochester.edu
1997urresearch.rochester.edu
Schaefer (1978) introduced a generalized satisfiability problem SAT (S) and showed that,
depending on the nature of relations in S, SAT (S) is either in P or NP-complete. A similar
result holds for generalized satisfiability with constants SAT_ {C}(S)(the version of the above
problem where constants are allowed). We study the possibility to obtain a version of
Schaefer's dichotomy theorem for instances satisfying an additional constraint, namely each
variable appears at most twice. We prove several partial results on the complexity of the …
Abstract
Schaefer (1978) introduced a generalized satisfiability problem SAT (S) and showed that, depending on the nature of relations in S, SAT (S) is either in P or NP-complete. A similar result holds for generalized satisfiability with constants SAT_ {C}(S)(the version of the above problem where constants are allowed). We study the possibility to obtain a version of Schaefer's dichotomy theorem for instances satisfying an additional constraint, namely each variable appears at most twice. We prove several partial results on the complexity of the versions SAT (S, 2), SAT_ {C}(S, 2) of the above two problems that take into account this restriction. We obtain a dichotomy theorem for SAT_ {C}(S, 2) in the case when all relations in S are symmetric.
urresearch.rochester.edu
以上显示的是最相近的搜索结果。 查看全部搜索结果