The complexity of variants of 3-SAT and NOT-ALL-EQUAL 3-SAT is well studied. However, in contrast, very little is known about the complexity of the problems' quantified counterparts. In the first part of this pape...
详细信息
The complexity of variants of 3-SAT and NOT-ALL-EQUAL 3-SAT is well studied. However, in contrast, very little is known about the complexity of the problems' quantified counterparts. In the first part of this paper, we show that for all there exists 3-SAT is Pi(p)(2)-complete even if (1) each variable appears exactly twice unnegated and exactly twice negated, (2) each clause is a disjunction of exactly three distinct variables, and (3) the number of universal variables is equal to the number of existential variables. Furthermore, we show that the problem remains Pi(p)(2)-complete if (1a) each universal variable appears exactly once unnegated and exactly once negated, (1b) each existential variable appears exactly twice unnegated and exactly twice negated, and (2) and (3) remain unchanged. On the other hand, the problem becomes NP-complete for certain variants in which each universal variable appears exactly once. In the second part of the paper, we establish r qcompleteness for for all there exists NOT-ALL-EQUAL 3-SAT even if (1') the Boolean formula is linear and monotone, (2') each universal variable appears exactly once and each existential variable appears exactly three times, and (3') each clause is a disjunction of exactly three distinct variables that contains at most one universal variable. On the positive side, we uncover variants of for all there exists NOT-ALL-EQUAL 3-SAT that are co-NP-complete or solvable in polynomial time. (C) 2020 Elsevier B.V. All rights reserved.
We consider a simplified version of NOT-ALL-EQUAL 3-Sat, a variation of the famous SATISFIABILITY problem, where each clause is made up of exactly three distinct literals and the question is whether there exists a tru...
详细信息
We consider a simplified version of NOT-ALL-EQUAL 3-Sat, a variation of the famous SATISFIABILITY problem, where each clause is made up of exactly three distinct literals and the question is whether there exists a truth assignment such that for each clause at least one literal is set to true and at least one is set to false. We show that NOT-ALL-EQUAL 3-Sat remains NP-complete if (1) each variable appears exactly four times, (2) there are no negations in the formula, and (3) the formula is linear, i.e., each pair of distinct clauses shares at most one variable. Therewith, we improve upon two results in the literature. (C) 2020 Elsevier B.V. All rights reserved.
暂无评论