Problemas de decisión completos de NP: ¿qué tan cerca podemos llegar a una solución?

Question

Después de demostrar que un cierto mejoramiento El problema es NP -Hard, el siguiente paso natural es buscar un algoritmo polinomial que se acerque a la solución óptima, preferiblemente con un factor de aproximación constante.

Después de demostrar que un cierto decisión El problema es NP-COMPLETO, ¿cuál es el siguiente paso natural? Obviamente no podemos "aproximarse" a un valor booleano ...

Supongo que el siguiente paso es buscar un algoritmo aleatorizado que devuelva la solución correcta con una alta probabilidad. ¿Es esto correcto?

Si es así, ¿qué probabilidad de ser correctos podemos esperar obtener de un algoritmo tan aleatorizado?

Por lo que entiendo en Wikipedia, PP contiene NP. Esto significa que, si el problema está en NP, debería ser fácil escribir un algoritmo que sea correcto más de $ 0.5 $ de los tiempos.

Sin embargo, No se sabe si BPP contiene NP. Esto significa que puede ser difícil (si no imposible) escribir un algoritmo que sea correcto más de $ 0.5+ Epsilon $ de The Times, por cada positivo $ epsilon $ independiente del tamaño de la entrada.

¿Entendí correctamente?