Problèmes de décision NP-Complete - À quelle distance pouvons-nous arriver à une solution?

Question

Après avoir prouvé qu'un certain optimisation Le problème est NP-Durn, l'étape naturelle naturelle consiste à rechercher un algorithme polynomial qui s'approche de la solution optimale - de préférence avec un facteur d'approximation constant.

Après avoir prouvé qu'un certain décision Le problème est NP-Complete, quelle est la prochaine étape naturelle? De toute évidence, nous ne pouvons pas "approximer" une valeur booléenne ...

Je suppose que la prochaine étape consiste à rechercher un algorithme randomisé qui renvoie la solution correcte avec une forte probabilité. Est-ce correct?

Si oui, quelle probabilité d'être correct pouvons-nous nous attendre à obtenir d'un tel algorithme randomisé?

Pour autant que je comprends de Wikipedia, PP contient np. Cela signifie que, si le problème est en NP, il devrait être facile d'écrire un algorithme qui est correct de plus de 0,5 $ de l'époque.

Cependant, On ne sait pas si BPP contient NP. Cela signifie qu'il peut être difficile (voire impossible) d'écrire un algorithme qui est correct de plus de 0,5 $ + epsilon $ de l'époque, pour chaque $ epsilon $ indépendant de la taille de l'entrée.

Ai-je compris correctement?