Tracks from hell — When finding a proof may be easier than checking it