Question

(complexity) prove: if P=NP, then there's an algorithm with a polynomial running time for the following problem:

input: a boolean formula φ
output: a satisfying assignment of φ if φ satisfiable. if φ not satisfiable, a "no" will be returned.

explanation: the algorithm accepts φ as an input (boolean formula). if φ doesn't have a satisfiable assignment, a "no" is returned. if φ does have a satisfiable assignment, one of the satisfying assignment is returned,. so we assign 0 or 1 to the variables of φ so that the value of φ in the assignment is 1.

b) using a), show that : if NP⊆BPP, then NP=RP.

Answer 1

Suppose consider the problem gven in (a) 1s SAT oblern ou suppose, SAT є BPP Using the boocting aiqument, uue can assume -that -there is a bobobilistic bolqnomial time Turi Mochine Mwbioba bility at least -ik out 2 corredt ansuer on any npur ot site k Coniderhe below algorithm: Ini halite φ -to be 3 using a neu) Rur M with in Maccetrs, keep xk set to o in M rejects. Change 4, Ы şetting k 6 instead Check -that -the current settin variables satisfies the original Φ, f so, accept or Reject- Scanned with CSI CamScanner

Ts not satis fiable, Hhere uwî ot be no Seing o the variables that w saris alqorithm vosil reject- J ,,осе ф ß satisfiable"-he þacba bility ota run teraHon cutbuts the o anq particular incorect answer -> k. Since -the Size φ,the obabitity ot faiture does no change cach Tteratton ar least the number o nce the size ariableSL k. 2 2 -the 'uns The boo bability -Hafan M makes an error s at most, s a randomi zed algoritbm -that th one- sided error, The algori thm cecides SAT SAT C BP.P So, Given NP BPP, fiom above Proot RP - NP Scanned with CamScanner