[40] Prove the following: (a) There is a sparse set in NP P iff NE = E. (b) Define E 2 analogous to p

[40] Prove the following:

(a) There is a sparse set in NP − P iff NE = E.

(b) Define ΔE 2 analogous to Δp 2 (Definition 1.7.10 on page 40). If NE =

ΔE 2 , and every sparse set in NP is polynomial-time many-to-one reducible

(Definition 1.7.8 on page 39) to SAT  C[log n, n2, ∞], then NE = E.

Therefore, all sparse sets in NP are in P.

Comments. For Item (b), use the Berman–Mahaney tree-labeling technique in [S. Mahaney, J. Comput. System Sci., 25(1982), 130–143].