# What is so fundamental about polynomial functions that they are used to demarcate the Hardness boundary in NP complexity classes?

This question has been bugging me ever since I first came across the concept of NP, NP-Complete, and NP-Hard a few years back: what is so fundamental about the polynomial functions that they are used to demarcate the boundary between what is "hard" and what is not?

I mean, it could have been many other ways, say:

1. Linear Functions: anything above linear (say polynomial or exponential) would become hard
2. Exponential Functions: anything above exponential (say factorial) would become hard
3. Sub-exponential: anything above sub-exponential (say exponential) would become hard

So, what's so fundamental about polynomials? Is it just an arbitrary human classification, or is there some deeper fundamental (mathematical or universal) truth to this choice?

New contributor
shivams is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• @user541686 Thanks for pointing that out. I fixed it. Sub-exponential is what I had in mind. Commented Aug 1 at 18:02
• Possibly also useful: Why are Polynomial Time Problems Considered Tractable, and Larger Times are Not? discusses what happens to various algorithms when you run them on next year's model computer, which is twice as fast as the one you currently own. Commented 2 days ago

## 2 Answers

I see two main reasons:

• Pragmatic reasons: It is a reasonable dividing line for most problems that arise in practice. Most problems that people encounter in practice seem to have time complexity something like $$O(n)$$, $$O(n \log n)$$, $$O(n^2)$$, $$O(n^3)$$, $$O(2^n)$$, etc. You'll see that there is a big gap there: there are not many algorithms that fall in the intermediate zone (i.e., super-polynomial but sub-exponential running time). Consequently, "polynomial or not?" does a pretty good job of separating the algorithms that are feasible from those that are not, for most problems we encounter in practice. Definitely not perfect, and there absolutely are counter-examples, but it's pretty good.

For example, if you run across a real-world problem in practice, and then I tell you that there is a polynomial-time algorithm for it, then empirically it is likely that there is a practical algorithm for it. Not always, it's not guaranteed, but this rule of thumb seems to hold reasonably well in practice. In particular, this means that the theory (which is framed in terms of worst-case polynomial running time) makes predictions that are reasonably accurate in practice.

• Theoretical reasons. This dividing line has some nice theoretical properties that are convenient for building a clean mathematical theory. For instance, polynomials are closed under composition, which means that if you have an algorithm that does a polynomial number of steps and calls a subroutine that runs in polynomial-time, the result also runs in polynomial time. This makes it easier to prove many theoretical results, and enables faster progress from theoreticians. It abstracts away aspects of the problem (e.g., $$O(n^2)$$ vs $$O(n^3)$$) that are less important and enables theoreticians to focus more narrowly on a particular, cleanly-specifiable mathematical problem.

Also, for almost every implementable model of computation we know, if it runs in polynomial time on that model of computation, it runs in polynomial time on essentially every other model of computation that can be instantiated in practice. This means that the theoretical model is robust to minor details in how computers are formalized. This too is convenient for building a theoretical foundation.

When you combine these two -- a clean formalization that enables theoreticians to make more progress, and reasonably accurate predictions in practice -- we obtain a mathematical theory that is both deep and useful.

There is a lot written on this subject. Please read Why polynomial time is called "efficient"?, Why are Polynomial Time Problems Considered Tractable, and Larger Times are Not?, Why is "P vs. NP" necessarily relevant?, Polynomial-time algorithms with huge exponent/constant, and these lecture notes to learn more. (Thanks to Mark Dominus for providing one of these links.)

• Thanks. That second point is what I was interested in knowing. I will go through the references. Commented Jul 31 at 23:41
• 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. Commented 2 days ago
• 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”. Commented 2 days ago
• 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$. Commented 2 days ago
• 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. Commented 2 days ago

Another reason: Polynomial hardness arises naturally in settings with randomness or probability: We often joke that you can probably prove approximately all of the fundamental results in ML theory with concentration bounds (Chernoff or Hoeffding) and a simple union bound.

If you use a concentration bound, then you probably end up finding that you need a polynomial number of samples before you can get a good estimate of the thing you're trying to estimate.

Take a look at one of the many ways to write a Chernoff bound: $$\Pr[X < (1-\epsilon)\mu] < \exp(-\mu\mathbf{\epsilon^2} /2)$$ It basically says that the probability of observing a particular set of events (such as a given number of heads when you're flipping coins) decreases exponentially with distance $$\epsilon$$ from the expectation. simply put, this shows that weirder sets of events are less likely by a boundable amount.

But if you rearrange this, then you'll notice that the number of samples you need to learn something within an error $$\epsilon$$ of your choice (e.g. a 95% confidence interval) increases with $$\epsilon^2$$, which is a polynomial.

This idea gets applied ubiquitously, and the result is that a huge number of provable results we have in ML theory say we can learn something so long as we have polynomial samples (polynomial as a function of the error we're willing to tolerate).

New contributor
cataclysmic is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.