Méthodes pour prouver la limite supérieure sur les algorithmes d'approximation A? [fermé

Question

Je fais face à des algorithmes simples randomisés et en ligne, les deux aimables produisent une certaine borne inférieure / supérieure sur la qualité de l'instance de sortie.

Par exemple, il existe un simple algorithme randomisé pour le Max-e3sat Problème, où il y a $ m $ clauses composé de trois variables distinctes de 3 variables dans $ {x_1, ..., x_n } $.

Il y a un théorème selon lequel s'il existe un algorithme qui est $ ( frac {7} {8} + epsilon) $ - approximation, alors $ p = np $.

Quelle méthode puis-je et dois-je utiliser pour prouver de tels théorèmes? Pourriez-vous s'il vous plaît donner un exemple?

Plus fini, concernant le Max-e3sat Problème, quelle méthode peut et dois-je utiliser pour prouver une telle affirmation:

Pour n'importe quel instant de Max-e3sat L'optimum est au moins $ frac {7m} {8} $? Je ne cherche pas la preuve de cette affirmation, juste la méthode pour le prouver.

Merci beaucoup