0

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.

Colonizor48
  • 419
  • The Hamiltonian Circuit problem tends to be easy "on average" with an appropriate definition of "on average". Note, that link includes links to other examples. – lulu Aug 31 '23 at 19:38
  • @lulu I am mostly interested in problems well beyond NP that are still easy on average. – Colonizor48 Aug 31 '23 at 19:41
  • Classical algorithms usually feature much smoother behavior. Simplex algorithm for linear optimization is considered as "strange" because it is $2^n$ on worst case but polynomial on average, and that is still much more regular than what you are asking for. In fact, that's to be expected: an algorithm with too wild complexity depending upon the input would not be retained by the community. So it depends on what you call "natural" examples. – Jean-Armand Moroni Aug 31 '23 at 19:53
  • @Jean-ArmandMoroni I was thinking problems where the most efficient algorithm for them is relatively easy on average, but still hard for some instances. Albeit the subset of "hard" instances could have measure 0. Something like a NEXPTIME or RE complete problem that can be solved in polynomial time on average, or perhaps even for almost all instances. For linear optimization, algorithms that always run in polynomial time are known. Or proof such algorithms cannot exist. – Colonizor48 Aug 31 '23 at 20:06

1 Answers1

0

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

Colonizor48
  • 419