Résumé : Approximation methods and probabilistic algorithms are two important ways to obtain efficient algorithms giving approximate solutions to hard problems. We give some examples from optimization, counting and verification problems. Property testing is also a very efficient method to approximate verification problems.
complexity - difficult problem - approximation - probabilistic approximation schemes - optimization - counting
verification - property testing