Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

6
  • $\begingroup$ Thanks. That second point is what I was interested in knowing. I will go through the references. $\endgroup$ Commented Jul 31, 2024 at 23:41
  • $\begingroup$ The naïve solution of the Travelling Salesman Problem runs in sub-exponential time. For n cities, it takes n! steps. But the problem size is s = n^2, so it takes (sqrt (s)) ! steps. $\endgroup$ Commented Aug 2, 2024 at 7:49
  • $\begingroup$ And many hard problems people have worked hard to make solutions faster without analysing if the result is exponential or sub-exponential; the interesting question is “which is the largest n where I can find a solution”. $\endgroup$ Commented Aug 2, 2024 at 7:52
  • 3
    $\begingroup$ That second point is the key point. Polynomial expressions are what is called a "free ring", which is the smallest set generated by a family of constants (here, operations with constant run times) and a single variable (the input parameter $n$) and the operations of addition (sequencing of algorithms with run times $a$ and $b$ has run time $a+b$) and multiplication by $n$ (iterating an algorithm with run time $r$ has run time $nr$). So once you allow iteration over an input of length $n$, you get the ability to write a program whose run time is $P(n)$ for any polynomial function $P$. $\endgroup$ Commented Aug 2, 2024 at 16:04
  • $\begingroup$ These two points actually contradict somewhat, because the problems we see "in practice" are not closed under composition. $(n^3)^3$ is no longer a commonly-seen complexity of a computational problem, by your figuring. $\endgroup$ Commented Aug 2, 2024 at 17:47