Problemi di decisione di NP -completi: quanto possiamo avvicinarci a una soluzione?

Question

Dopo aver dimostrato che un certo ottimizzazione Il problema è NP -hard, il prossimo passo naturale è quello di cercare un algoritmo polinomiale che si avvicina alla soluzione ottimale, preferibilmente con un fattore di approssimazione costante.

Dopo aver dimostrato che un certo decisione Il problema è NP-completo, qual è il prossimo passo naturale? Ovviamente non possiamo "approssimare" un valore booleano ...

La mia ipotesi è che il prossimo passo è cercare un algoritmo randomizzato che restituisca la soluzione corretta con un'alta probabilità. È corretto?

In tal caso, quale probabilità di essere corretti possiamo aspettarci di ottenere da un algoritmo così randomizzato?

Per quanto ho capito da Wikipedia, PP contiene NP. Ciò significa che, se il problema è in NP, dovrebbe essere facile scrivere un algoritmo che è corretto più di $ 0,5 $ di tempi.

Tuttavia, Non è noto se BPP contiene NP. Ciò significa che, può essere difficile (se non impossibile) scrivere un algoritmo che è corretto più di $ 0,5+ epsilon $ dei tempi, per ogni $ epsilon $ indipendentemente dalla dimensione dell'input.

Ho capito correttamente?