Number of equivalence classes in $P$
-
05-11-2019 - |
Pregunta
I am currently taking a course which involves computational complexity. I was told that polynomial equivalence (polynomial time reduction) divides P into exactly 3 equivalent classes, namely $\phi$ , $\Sigma^*$ and $P - \{\phi,\Sigma^*\}$. I am unable to figure out how this is true, specifically how if $L_1,L_2 \in P, L_1 \sim_P L_2$. I think there's a simple fact/idea I am missing out on, but I don't know what it is.
No hay solución correcta
Licenciado bajo: CC-BY-SA con atribución
No afiliado a cs.stackexchange