PROOFS

Types of proofs for problems, objects, statements,...

Proof types for algos

Induction Proofs

When applicable?

When the statement involves discrete structures, numbers, words, etc., and the statement can be derived from the statement for a smaller structure.

Existence Proofs

Prove that object X exists. Refute that object X does not exist.: Example!!! or construction method (with its own correctness proof)

Prove that object X does not exist. Refute that object X exists.: An example of an object Y ̸= X is not sufficient! Similarly, it is not enough that a specific algorithm does not yield the desired result

Proof by contradiction

When the opposite assumption is easy to refute. Typical applications:

Uniqueness proofs, existence proofs, correctness proofs.

Runtime Proofs

To determine the runtime of non-recursive algorithms, it is sufficient to sum up

the number of elementary instructions, where the number of instructions in

loops is multiplied by the number of loop iterations.

For recursive algorithms, the recursive runtime formula is established and

analyzed.

Correctness Proofs

The goal is usually to show that a given algorithm always delivers the desired

result on any input.

Here, it is not enough to provide a successful example!

Classical approaches are identifying + inductive proving of loop invariants in

round-based algorithms or also proof by contradiction (assumption: algorithm

does not deliver correct result).

Quality Proofs

Here, the goal is to show that an APX algorithm delivers a result that is

guaranteed to be only a limited distance from the optimum.

The approach usually consists of finding one or more bounds for the optimum

and relating the bounds to the APX solution.