Sia $f$ una funzione polinomialmente riducibile ad una funzione $g$, ovvero esiste una funzione $\rho \in P$ tale che $f(x_1, x_2, ..., x_n) = g(\rho(x_1, x_2, ..., x_n))$, allora:
1) $g \in P \Rightarrow f \in P$
2) se $f \in P$ non è detto che $g \in P$
Quello che non riesco a capire è la parte 2). Qualcuo mi sa dire come si può dimostrare tale proposizione?
Grazie