2 added 7 characters in body
source | link

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 literalsvariables are TRUE. b

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

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

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.

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 literals 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 such formulae... We'd also like some hints on how to reduce to these problems.

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
source | link

2 SAT variants complexity class

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 literals 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 such formulae... We'd also like some hints on how to reduce to these problems.