Your manager calls you into the office with the following comment: We are now moving into the business of Boolean formula satisfiability. Starting next month, every morning we will be receiving a large number of large Boolean formulas. For each formula, we will need to determine if it is satisfiable. Note that we do not have to actually find the satisfying assignment; we just need a YES/NO answer for each formula. gain we need your unique skills. You have two weeks to write a lightning fast program to solve satisfiability for these formulas. Of course, you have no idea how to write such a program. You scour the internet but cannotfind a satisfactory program to solve satisfiability for Boolean formulas. However, you do find agreat program to solve satisfiability for Boolean circuits.

Required:
a. Explain very briefly in English how you would use this Boolean circuit program to solve satisfiability for Boolean formulas.
b. Assume that the Boolean circuit satisfiability program works in linear time e(m), where m is the number of gates and/or wires in the Boolean circuit. How fast can you determine if a formula with n connectives is satisfiable? Justify.
c. Assume that the Boolean circuit satisfiability program works in time (m"), where m is the number of gates and/or wires in the Boolean circuit. How fast can you determine if a formula with n connectives is satisfiable? Justify.