We survey research that studies the connection between the computational complexity
of optimization problems on the one hand, and the duality gap between the primal and
dual optimization problems on the other. To our knowledge, this is the first survey that
connects the two very important areas. We further look at a similar phenomenon in finite
model theory relating to complexity and optimization.