¿Por qué las igualdades entre clases de complejidad se traducen hacia arriba y no hacia abajo?
Hola chicos, entiendo que el truco de relleno nos permite traducir clases de complejidad hacia arriba - por ejemplo, . El relleno funciona "inflando" la entrada, ejecutando la conversión (digamos de N P a P ), lo que produce un algoritmo "mágico" que puede ejecutar en la entrada rellenada. Si bien...