“ SAT in polynomial time – Yes, it’s possible!! ” You are given Hint. (a or b) a

Question

“SAT in polynomial time – Yes, it’s possible!!” You are given

Hint. (a or b) and (not b or not c) is equivalent to writing: (a or not c).

following format: (x1 or x2) and (x3 or x4) ..... That is, the SAT formula has a list of conjunctions (AND

a SAT formula of the

symbol), and each conjunction consists of exactly two disjunctions (literal connected by OR connector).

Describe an efficient algorithm to find an assignment of truth-values to literals such that the formula is

true, or report that the formula is not satisfiable. Surely, your “efficient” algorithm should run in

polynomial time

Explanation / Answer

One of the efficent algorithm for this problem is GSAT. It is based on a randomized
local search engine. This algorithm starts with generated truth assignment. It will
flip the assignment of an variable so that it leads to the greatest decrease in the
total number of unsatisfied clauses. This explaination is cinsidered to be an flip.
Suh flips are will repeat until satisfied assignment is found or pre-set maximum
number of flips is reached (Mac-Flips). This process repeats upto maximum of MAX-TRIES
times.
The search of GSAT typically with rapid greedy descent towards better assignment followed
by sideways.

GSAT (F)
Input : A CNF formula F
Parameters : Integers MAX-FLIPS, MAX-TRIES
Output : A satisfying assignment for F, or FAIL
begin
for i 1 to MAX-TRIES do //until max tries found
a randomly generated truth assignment for F
for j 1 to MAX-FLIPS do //until max flips found
if satisfies F then return // if found success
v a variable flipping which results in the greatest decrease
(possibly negative) in the number of unsatisfied clauses
Flip v in
return FAIL // if none of the satisfying assignment found
end

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.