Many combinatorial problems that come up in the real world have been classified as NP-hard [Garey and Johnson 1979]. An example is the following task: After a series of experiments, certain pairs of experiments are found to have conflicting results. We therefore know that for each pair, at least one of the experiments was faulty. We now want to find the minimum number of experiments to discard such that there are no more conflicts. This problem, in its abstract form as a graph problem, is known as Vertex Cover, where given a graph, we search for a minimum number of vertices to delete to get rid of all edges. It is by now an established assumption that NP-hardness implies an inherent combinatorial explosion in the solution space that leads to running times growing exponentially with the input size. This means that large instances of NP-hard problems cannot always be solved efficiently to optimality.