3a asks to prove that any problem where the number of bits in the witness is O(log(n)) is in complexity class P

3b asks to explain why using brute force to solve problems where the number of bits in the witness scale polynomially with n takes exponential time.

(20 pts extra credit) In the review session for his Deep Wizarding class, Dumbledore reminds everyone that the logical definition of NP requires that the number of bits iin the witness w is polynomial in the number of bits of the input n. That is, poly(rn). With a smile, he says that in beginner wizarding, witnesses are usually only logarithmic in size, .e.,O(ogn) (a) Because you are a model student, Dumbledore asks you to prove, in front of the whole class, that any such property is in the complexity class P. b) Well done, Dumbledore says. Now, explain why the logical definition of NP im- plies exponential time for any brute force algorithm