Esercizi

Domanda 1 di 44 · Complessità

Che cosa garantisce un algoritmo di approssimazione?

• La soluzione ottima, ma in tempo esponenziale sui problemi difficili
• Una soluzione subottima senza alcuna garanzia, in tempo polinomiale
• La soluzione ottima in tempo polinomiale anche sui problemi NP-ardui
• Una soluzione subottima con una garanzia sulla qualità, in tempo polinomiale

Complessità

Modello RAM