Domanda

Attualmente sto seguendo un corso che comporta la complessità computazionale. Mi è stato detto che l'equivalenza polinomiale (riduzione del tempo polinomiale) divide P in esattamente 3 classi equivalenti, vale a dire $ phi $ , $ Sigma^*$ e $ P - { phi, Sigma^*} $. Non sono in grado di capire come sia vero, in particolare come se $ L_1, l_2 in p, l_1 sim_p l_2 $. Penso che ci sia un semplice fatto/idea che mi sto perdendo, ma non so cosa sia.

Nessuna soluzione corretta

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange
scroll top