Prove each of the following:

a. If A, B NP, then A B NP.

b. If A, B NP, then A B NP.

c. If A, B NP, then A B NP, where A B = { xy | x A and y B }.

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 )