1 Introduction

2 Quite Old Complexity Results that Limit the Performance of Heuristic Algorithms
2.1 Low Error Frequency and Speeding-Up-SAT Consequences
2.2 Padding, and What Error Frequencies Can We Expect?
2.3 The 1970s, Berman-Hartmanis, and Inheritance of Frequency of Correctness: If I'm Frequently Easy, Then So Are All These Famous Problems

3 Deterministic Heuristic Algorithms for Problems Solvable With Randomness

4 When Heuristics Fail Often in Theory But Work Well In Reality
4.1 Compressible Instances
4.2 The Distance from Practical Instances to Theoretically Easy Instances