Question

In the MAX SAT problem, we are given a set of clauses, and we want to find an assignment that satisfies as many of them as possible.

(a) Show that if this problem can be solved in polynomial time, then so can SAT.

(b) Here’s a very naive algorithm.

for each variable:

set its value to either$\mathbf{0}\mathbf{}\mathit{o}\mathit{r}\mathbf{}\mathbf{1}$ by flipping a coin

Suppose the input has m clauses, of which the$\mathbf{jth}$ has${\mathit{k}}_j$ literals. Show that the expected number of clauses satisfied by this simple algorithm is

$\sum _{j=1}^m\left(1-\frac{1}{2^k}\right)\ge \frac{m}{2}$

In other words, this is a 2-approximation in expectation! And if the clauses all contain literals, then this approximation factor improves to $\mathbf{1}+\mathbf{1}/\left({\mathbf{2}}^k-\mathbf{1}\right).$

(c) Can you make this algorithm deterministic? (Hint: Instead of flipping a coin for each variable, select the value that satisfies the most of the as of yet unsatisfied clauses. What fraction of the clauses is satisfied in the end?)

Short answer

This problem can be solved in polynomial time is shown below.

b). Thenaive algorithm is proved.

c). Yes, this algorithm is deterministic.

Step-by-step solution

MAX SAT problem

MAXSAT (the maximum satisfiability problem) is stated as follows is defined as given a set of clauses with weights, find a truth assignment that maximizes the sum of the weights of the satisfied clauses.

In the multiway cut problem, we are given a graph with k special vertices Our goal is to find the smallest set of edges which when removed from the graph disconnect the graph into at least k components where each is in a different component. When ,

this is exactly the min s-t cut problem, but if the problem becomes . Consider the following algorithm.

Let Fi be the set of edges in the minimum cut with si one one side and all other special vertices on the other side. And output is , the union of all . Also note that this is a multiway cut because removing from isolates in its own component.

MAX SAT problem can be solved in polynomial time.

MAX- SAT PROBLEM is solvable in polynomial time and two-SAT is -Hard.

MAX-two-SAT is -Hard and its decision version is NP-Complete, while two-SAT is in and hence also in . This means that 2-SAT is polynomial-time reducible to (the decision version of) MAX-2-SAT. The converse is not true unless = be a two-SAT formula with mm clauses. If you really want to reduce an instance of two-SAT to (the decision version of) MAX-two-SAT, then this simply amounts to checking whether at least mm (i.e., all) clauses of are satisfiable.

2SAT is the problem of counting the number of satisfying assignments to a given two-Chomsky normal form formula. This counting problem is -complete, which implies that it is not solvable in polynomial time unless = .

there are (this is a polynomial algorithms). We can bound this through some very simple observations.

1. Initially $\left|\text{E}\left(\text{S,S¯}\right)\right|\ge \text{0,}$

2. In every iteration,$\left|\text{E}\left(\text{S,S¯}\right)\right|$ increases by at least one, and

3.$\left|\text{E}\left(\text{S,S¯}\right)\right|$is always at most $m\ll n.$

Thus, the problem exhibits a phase transition at α = 1. In the maximum-2-satisfiability problem ( MAX-2-SAT ), the input is a formula in conjunctive normal form with two literals per clause.These facts in the graph$G=\left(V,E\right)$ clearly imply that the number of iterations is at most $m\ll n.$, and thus the total running time is polynomial. To prove the next theorem about the approximation ratio, we will do something which is very common when analyzing local search algorithms. We will not reason directly about the solution which the algorithm outputs, but will instead reason about an arbitrary local optimum. Since the algorithm outputs$\left(S,T\right)$ a local optimum,

Hence, MAX SAT problem is solved in polynomial time

Naive algorithm

Naive algorithm is exact string matching it means finding one or all exact occurrences of a pattern in a text algorithm. This algorithm is helpful for smaller texts. It does not need any pre-processing phases. We can find substring by checking once for the string.

for each variable.

set its value to either$0\mathrm{or}1$ by flipping a coin

Suppose the input has m clauses, of which the$\mathrm{jth}$ has$k_j$ literals. Show that the expected number of clauses satisfied by this simple algorithm is ,

$\sum _{j=1}^m\left(1-\frac{1}{2^k}\right)\ge \frac{m}{2}$

This is a 2-approximation in expectation! And if the clauses all contain literals, then this approximation factor improves to$1+1/\left(2^k-1\right).$

Deterministic Algorithm

Here, each coin of a given denomination can come an infinite number of times. (Repetition allowed), this is what unbounded knapsack and have two choices for a coin of a particular denomination, either

i) to include, or

ii) to exclude. But here, the inclusion process is not for just once; we can include any denomination any number of times until $N<0.$

Basically, If we are at $s\left[m-1\right]$, we can take as many instances of that coin is known as unbounded inclusion that is, $\mathrm{count}\left(\mathrm{S},\mathrm{m},\mathrm{n}–\mathrm{S}\left[\mathrm{m}-1\right]\right);$ then we move to After moving to $s\left[m-2\right].$, we can’t move back and can’t make choices for s[m-1] thart is$count\left(S,m,n–S\left[m-1\right]\right);$

Finally, as we have to find the total number of ways, so we will add these two possible choices, i.e $count\left(S,m,n–S\left[m-1\right]\right);$$+count\left(S,m-1,n\right);$

Instead of flipping a coin for each variable ,in first step just select the value that satisfies the most of the as of yet unsatisfied clauses. The definite fraction of the clauses is satisfied in the end.

Hence, each coin of a given denomination can come an infinite number of times. (Repetition allowed), this is what unbounded knapsack and have two choices for a coin of a particular denomination and this is deterministic in nature.