Show that if P NP then every language in P except ie the e

Show that if P = NP then every language in P except {} (i.e. the empty set) and * is NP-complete.

Solution

Let A be any language in NP and let B be another language not equal to or . Then there exist strings x B and y not belong to B. To reduce an instance w of A to that of B, we just check in polynomial time if w A. If yes, we output x and y when w not belong to A. The languages and cannot be NP-complete, because to reduce a language A to a language B, we need to map instances in A to instances in B and those outside A to outside B. However, for B = , there are no instances in B (and none outside B for B = ) which means there cannot be such a reduction from any language A not equal to , .