Prove each of the following. You may use any theorems proved in class.

1. If P NP, then P NPC = .

2. If A NPC, B NP, and B NPC, then A _p B is false.

Proved Theorems:

A = the set of all strings encoding satisfiable 3-cnf-formula

B= the set of all strings encoding all pairs of (G,k) such that G has a k-clique

Let M_B a poly-time decider of B

If A _p B and B P, then A P.

If A _p B and A P, then B P.

Let A,B,C ^* then 1. A _p B (reflexivity)

2. A _p B and B_p C => A _p C (transivity)

If A NPC, B NP, and A _p B, then B NPC.

If B P NPC (i.e B NPC ) then P = NP.

If B NP-P, then for all A NPC, A P. (i.e NP-P )