Algorithm that inputs a formula of propositional logic


Suppose you have an algorithm that inputs a formula of propositional logic and outputs eithere SAT or UNSAT. The algorithm runs in polynomial time and gives the correct answer with probablity at least 2/3 on any input. SHOW how to obtain a polynomial-time algorithm for the propositional satisfiability problem that outputs either SAT or UNSAT on all inputs, is always correct when it returns SAT, and is correct with probability 2/3 on all inputs.

Request for Solution File

Ask an Expert for Answer!!
Data Structure & Algorithms: Algorithm that inputs a formula of propositional logic
Reference No:- TGS095445

Expected delivery within 24 Hours