The following decision problem is called k-True-Monotone-2SAT:Given a 2-CNF boolean formula $F$ that does not contain any negated variables  and given a positive integer $k$, can $F$ be satisfied by setting $k$ or fewer  variables to true?It is NP-complete: it's easy to see a straightforward reduction from Vertex Cover to it (i.e. can we cover all the edges with $k$ or fewer nodes?).The following decision problem is called Monotone-2SAT:Given a 2-CNF boolean formula $F$ that does not contain any negated variables, is it satisfiable?As a decision problem, Monotone-2SAT is trivial. The answer is always YES: just set every variable to true.But consider its counting version, called #Monotone-2SAT:Given a 2-CNF boolean formula $F$ that does not contain any negated variables, how many satisfying assignments $F$ has?Surprisingly, #Monotone-2SAT is #P-complete.Now here is the question. Suppose we have an oracle for #Monotone-2SAT, which returns the exact solution count of a Monotone-2SAT formula: how such solution count can be used to solve k-True-Monotone-2SAT?I'm asking this because I do not immediately see how the solution count may give information on how many solutions have k or less literals set to true and how many don't.
Monotone-2SAT and Vertex Cover
cc.complexity theory;ds.algorithms;sat