Pourquoi les égalités entre les classes de complexité se traduisent-elles vers le haut et non vers le bas?
Hé les gars, je comprends que l'astuce de remplissage nous permet de traduire les classes de complexité vers le haut - par exemple . Le remplissage fonctionne en "gonflant" l'entrée, en exécutant la conversion (disons de à ), ce qui donne un algorithme "magique" que vous pouvez exécuter sur...