# How to proof a heuristic?

I am not very familiar with "heuristic", so please correct me if anything said by me is wrong.

Per my understanding, Algorithm is an automatic steps which guarantee to give a correct solution corresponding to a specific problem (and its input domain)

Heuristic is somehow a rule to guess the next step, hoping when repeating this rule a nearly-optimal solution is found.

Algorithm is proof-able, the complexity, the correctness, etc.

But I wonder how can one proof heuristic?

Indeed I wonder is "proof" a correct term / action correlate to heuristic, but how about say, proof the heuristic can give sub-optimal answer (like at most 10% worst than the optimal) for 90% out of all possible input?

• You must distinguish between what's commonly called a heuristic ("works well in practice, can be arbitrarily bad") and an approximation algorithm ("gives a result with a provable quality guarantee"). – adrianN Jul 27 '17 at 9:50
• What does "prove an algorithm" mean? I find it a meaningless phrase, so I couldn't start to guess what "prove a heuristic" means. – Raphael Jul 27 '17 at 15:38
• Sorry for all confusion, i try to rephrase here: to me the correctness of algorithm can be proved, the bound of its complexity can be proved as well. An algorithm is right or wrong. But heuristic does not work like that, so is there any way to prove how "good" or how effective is a heuristic? – shole Jul 27 '17 at 16:00

According to Wikipedia:

A heuristic technique (...) is any approach to problem solving, learning, or discovery that employs a practical method not guaranteed to be optimal or perfect, but sufficient for the immediate goals.

Thus you can employ a heuristic to design an algorithm. This would give suboptimal answers, however you can still state theorems that relate to the correctness of such algorithm:

For any $\epsilon>0$, the algorithm approximates the problem $P$ with a multiplicative factor $1+\epsilon$ in time $O(T(\epsilon))$.

which means that for every input, if the expected answer of $P$ is $y$ and your algorithm returns $y'$, then:

$$y\le y'\le (1+\epsilon)y$$

You can also bound the error with an additive factor for instance.

• For decision problems, if you fix a probability distribution on the input, you may state that your algorithm returns a correct answer with a probability of 90%. That would be a correctness result.

In any case you should keep in mind that a heuristic usually denotes general ideas applicable in many situations, which is said to work well empirically and for which you don't try to prove error bounds (such as in simulated annealing).