Exercici 7 (Tasca 7).
(P,
NP,
NP-completeness,
unary language)
Teorema de Berman
Un llenguatge s’anomena unari si cada mot que conté és de la forma 1^n per a algun n \ge 0.
Demostreu el teorema de Berman (1978): si un llenguatge unari és \mathsf{NP}-complet, aleshores \mathsf{P} = \mathsf{NP}.
Consell
Utilitzeu el fet que \mathtt{SAT} és \mathsf{NP}-complet i, per hipòtesi, reductible a un llenguatge unari mitjançant una funció f. Per decidir \mathtt{SAT}, donada una fórmula booleana d’entrada \phi, considereu l’arbre on l’arrel (nivell 0) és \phi i les fórmules al nivell k s’obtenen de les del nivell k-1 de manera que la k-èsima variable pren els 2 valors de veritat possibles. Demostreu com f permet explorar aquest arbre en temps polòmic.