Write a polynomial-time algorithm that finds a satisfying


In this problem assume that P has just been proven equal to NP, and so you have a polynomial time algorithm A that decides 3-SAT; that is, it takes in a logical formula written in 3-SAT form ((x1 V x2 V-x3) (-x1V x2 V x3) and it tells you whether or not a satisfying assignment exists for that formula (you also have a million dollars because you solved P = NP, but that's a different story...)

So you have an algorithm A that tells you whether or not a satisfying solution exists for a logic formula, but you don't have one that tells you what exactly that satisfying solution is.

For this problem, write a polynomial-time algorithm that finds a satisfying solution to an instance of 3-SAT, given that you have a polynomial-time algorithm A you can run that tells you whether or not a solution exists to an instance of 3-SAT.

Request for Solution File

Ask an Expert for Answer!!
Computer Engineering: Write a polynomial-time algorithm that finds a satisfying
Reference No:- TGS02897468

Expected delivery within 24 Hours