Mini #6, 15451 Fall 2010
        ========================

This mini is due via *email* to your TA, by 11:59pm Tuesday, Nov 23.
Please use the *exact* subject line "15-451 MINI #6" in your email.
As always make sure to include your name and Andrew ID.

Also, we prefer that you copy your answers directly into the email body, instead
of including attachments. Thanks!

1.  Assume problems A and B are both contained in NP.  Suppose that we have an 
efficient (polynomial time) reduction from problem A to problem B. This would 
imply:
a. Problem B is NP-Complete
b. Problem A is NP-Complete
c. An efficient algorithm to solve problem A could be used to solve problem B 
efficiently.
d. An efficient algorithm to solve problem B could be used to solve problem A 
efficiently.
e. If problem A is NP-Complete then problem B must also be NP-Complete
f. If problem B is NP-Complete then problem A must also be NP-Complete

(List *all* of the correct answers)


2.
(a)  What is  5^11 mod 7 ? Use the fast modular exponentiation algorithm, and 
show your work.


(b) What is 47^{-1} mod 451?  (the multiplicative inverse of 47)
Use the extended GCD algorithm, and show your work.


(c) What's the multiplicative inverse of 16 mod 17? What's the inverse of 10 mod 
11? Can you explain why?