[29] Let g(n) ≤ n be an unbounded, monotonically increasing function and let G(n) be such that for every k, limn→∞ nk/G(n)=0.

Show that C[g(n), G(n), ∞]

 SAT ⊆ A0 ⊂ SAT and A0 ∈ P implies that SAT is not P-isomorphic to SAT − A0. Also show that SAT − A0 is NP-complete.