Question: Which of the following languages are in P? which in NP? other classes?

a. EXACTLY-2-CNF (every clause in the formula has 2 differenet literelas)- does there exist a satisfying assignment s.t. at most k variables are TRUE.

b. same language but this time in each clause one literal is negated and the other isn't.

c. SAT-2-NAE - every clause has exactly 2 literals, is there an NAE satisfying assignment to the formula

d. mono-SAT-2-NAE - every clause as exactly 2 literals, none of them negated and it has a satisfying assignment

Thoughts: We tried a lot of reductions from 2SAT and other problems and cannot really determine most of the questions. We'd like to know what is the effect of the "monotone" property on the satisfiability such formulae... We'd also like some hints on how to reduce to these problems.

  • 1
    $\begingroup$ a. is at least as hard as vertex cover. ​ ​ ​ ( variables -> vertices ​ and ​ clauses -> edges ) ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user12859
    Jan 10, 2016 at 14:38
  • 1
    $\begingroup$ Does "at most k literals are TRUE" also apply to c and d? ​ ​ $\endgroup$
    – user12859
    Jan 10, 2016 at 14:38
  • 1
    $\begingroup$ At most $k$ literals are TRUE doesn't make sense. Perhaps you meant at least $k$ variables are TRUE? $\endgroup$ Jan 10, 2016 at 15:08
  • $\begingroup$ "Monotone" means there are no negated literals. $\endgroup$ Jan 10, 2016 at 17:04
  • $\begingroup$ Ricky: no. Yuval: yes (vars in the assignment) $\endgroup$
    – jreing
    Jan 10, 2016 at 19:35

1 Answer 1


b. is completely trivial - just set each variable to FALSE.

d. trivially reduces to c. ​ ​ ​ c. reduces to d. as follows:
For each double-negative clause, remove the negatives. ​ Replace each
single-negative clause with 2 clauses, each of which has one of the original clause's variables
and a new variable that's shared with the other of the 2 new clauses but otherwise unused.

That works because:
for 2-variable clauses, NAE is just ≠
for boolean variables, ​ ​ ​ x ​ NAE ​ not y ​ ​ ​ simplifies to ​ x = y
for boolean variables, [there exists a y such that ​ ​ ​ x ≠ y ​ and ​ y ≠ z ] ​ if and only if ​ x = z

By ​ ​ ​ variables <-> vertices ​ and ​ clauses <-> edges ​ , ​ ​ ​ c. is equivalent to bipartiteness.
Bipartiteness is logspace-complete. ​ (Thus, c. and d. are logspace-complete.)

By throwing in k extra variables to handle "at most" vs. "exactly", a. is in W[P].
By ​ ​ ​ vertices -> variables ​ and ​ edges -> clauses ​ , ​ ​ ​ vertex cover reduces to ​ a. .
(Thus, for unrestricted k, a. is NP-complete.) ​ However, a. is fixed-parameter tractable.

By replacing each clause with k+1 copies of itself and then [for each variable, putting in a
clause whose literals are both the negation of that variable], a. reduces to Almost 2-SAT.
By part 2.1 of that paper, that paper handles the case of clauses whose 2 literals are the same.
Theorem 7 of that paper explicitly covers "possible repeated occurrences of clauses".

I have no clue regarding possible kernalizability of a. or
$\big[$the space requirements of algorithms for a. whose runtimes aren't ​ max$\hspace{-0.03 in}\big(\hspace{-0.04 in}$nΩ(k),$\hspace{.02 in}$2Ω(n)$\hspace{-0.03 in}\big)\big]$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.