Average-case complexity without the black swans