Are there arbitrarily hard worst case problems that are (relatively)easy on average? For example, could there be an RE complete problem that is solvable in polynomial time for most instances? It think it should be easy to construct such problems artificially by padding, but are there any natural examples? For example, a problem in EXPTIME that is P on average, or a problem in say $\Sigma^0_2$ that is DLOGTIME on average. Or even a problem that say is not in PR, but is NP(as in, relatively easy compared to worst case complexity) on average.
2026-04-02 10:00:47.1775124047
Are there(preferably natural) arbitraraly hard problems in the worst case that are easy on average?
50 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
Yes. For example, the halting problem, while undecidable, is actually decidable in linear time on almost all inputs. See https://en.wikipedia.org/wiki/Generic-case_complexity