Exercise 7 (Homework 7).
(P,
NP,
NP-completeness,
unary language)
Berman’s theorem
A language is called unary if every string in it is of the form 1^n for some n \ge 0.
Prove Berman’s theorem (1978): if a unary language is \mathsf{NP}-complete, then \mathsf{P} = \mathsf{NP}.
Tip
Use the fact that \mathtt{SAT} is \mathsf{NP}-complete and, by hypothesis, reducible to a unary language via some function f. To decide \mathtt{SAT}, given an input Boolean formula \phi, consider the tree whose root (level 0) is \phi and whose formulas at level k are obtained from the ones at level k-1, where the k-th variable takes the 2 possible truth values. Show how f allows us to explore this tree in polynomial time.