What is a natural problem in theory of computation?

Question

In Stephen Cook's paper on the P vs NP problem,[1] he states the following [2]:

Feasibility Thesis: A natural problem has a feasible algorithm iff it has a polynomial-time algorithm.

My question is, what exactly does he (or in general really, what does one) mean by "a natural problem"? Talking about problems being natural seems to be common enough, but I have yet to find a definition. I seem to be missing something. Here are a couple of possible answers I am thinking about:

First Possible Answer

Cook says in his paper that "natural" must be explained. He says, "generally we do not consider a class with a parameter as natural, such as the set of graphs embeddable on a surface of genus k, k > 1."[3] Now, first off, this seems to say what "natural" is not rather than what it is; but if every problem is either natural or not and this fully describes all problems that are not natural, then this would be enough to define natural. (But the qualifier "in general" suggests that this is not a sufficient and necessary description of problems that are not natural.)

I think "classes with parameters" is referring to fixed-parameter tractability, by which we mean problems that have possible inputs restricted such that feasibility is forced. So we can solve the knapsack problem[4] with a polynomial-time algorithm if we fix the weight the knapsack can carry (but in general there is no solution in polynomial-time). With this in hand, I take it that to be "natural" means the problem is not restricted ("artificially" restricted?) in a way that forces a polynomial-time algorithm out of a problem that is not solvable in polynomial time.

The reason I am not certain this the right way to understand Cook's notion of "natural" is that I'm not absolutely sure what the qualification "natural" is doing here. If you drop "natural," then you get "a problem has a feasible algorithm iff it has a polynomial-time algorithm." But this seems perfectly reasonable: the knapsack problem does not have a feasible algorithm because it does not have a polynomial-time algorithm; the knapsack-with-fixed-paramater-tractability has a feasible algorithm because it has a polynomial-time algorithm. Both accounts seem to be in accord with the notion of what a problem with a feasible algorithm is.

I take it this might be the best guide to understanding what Cook means, because Cook actually turns around and defines it. I also take it that this notion of natural is captured by this StackExchange question.[5}

But there is another.

Second Possible Answer

William Gasarch in his paper "Classifying Problems into Complexity Classes"[6], says he will conduct "a literal discussion what is a natural problem"[7]. At the close of the paper,[8] there is an exchange in dialogue form, where one speaker says:

"What makes a problem natural? On the one hand, I didn’t construct the problem for the sole purpose of not being in P. So it’s not a dumb ass problem. Does it then raise to the level of being natural?"

So it seems to me what Gasarch is saying is that if we have a problem that is not intentionally constructed so that we can say that it is not in P, then it is natural. So with a bit of creative interpretation, it seems like Gasarch is saying something at least consistent with Cook: on the one hand, Gasarch says not being constructed with the only goal not being in P makes a problem not natural; and on the other hand Cook says a problem is natural if it does not have parameters. But mere consistency does not yield a definition.

Third Possible Answer

On the Wikipedia entry for a "well-posed problem"[9], a definition of Jacques Hadamard's notion of a well-posed problem is presented, then it is stated that a well-posed problem "might be regarded as 'natural' problems in that there are physical processes modelled by these problems." So, a problem is natural if and only if it models a physical process?

Hadamard's qualifications, according to Wikipedia, are (i) a solution exists, (ii) the solution is unique, and (iii) the solution's behavior changes continuously with the initial conditions. This seems to be different from the other two definitions. My sense is that "natural" is not being used in exactly the same way (especially if we agree with the interpretation that a problem is natural if and only if it models a physical process), but I wanted to include it because I ran into it in my research on this question, and there are points of contact.

So my question is: what is a natural problem? Are any of these answers, or some combination of them, correct? Is there some other answer that I'm missing? Thank you.

1. "The Statement of the Problem," 2006, posted online at the Clay Mathematics; title: "The P vs NP Problem", http://www.claymath.org/sites/default/files/pvsnp.pdf
2. p. 3
3. p. 4
4. https://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_Knapsack_Problem
5. Hardest known natural problem in P? I take it that a natural problem follows this description but does not restrict k to being the largest.
6. https://www.cs.umd.edu/~gasarch/papers/classcomp.pdf
7. p. 2.
8. p. 47-8, section 25
9. https://en.wikipedia.org/wiki/Well-posed_problem

Answer 1

To be clear, it's not meant to be formalizable. It's not a theorem, it's an observation about the world -- it's okay if "natural" is subjective here. For analogy, if someone says "differentiation is mechanics while integration is art", they're not inviting you to formalize "mechanics" and "art" and prove the statement, they're trying to convey a general perspective. So you may be missing the forest a bit for the trees here.[footnote]

What's the author's point

Let's follow your suggestion and drop the word "natural":

Feasibility Thesis (first draft): A problem has a feasible algorithm iff it has a polynomial-time algorithm.

Well, this is technically wrong. Due to the time hierarchy theorem, we can construct arbitrarily hard problems in P (e.g. requiring $n^{1000}$ time). But these counterexample problems are very strange, self-referential, e.g. "does the given Turing machine halt on the given input in $n^{1000}$ steps?"

So the author feels the thesis is still pretty accurate regarding problems we actually want to solve in the real world and other problems encountered "naturally" in the course of non-complexity-theory life. So he thinks, let's call those problems "natural" and revise the feasibility thesis.

What is and isn't natural

For sure, a problem that arises commonly in practice would be considered natural: shortest paths, sorting, edit distance, root-finding, traveling salesman, knapsack.

For sure, a problem that is thought up and defined specifically to prove a complexity result, and references the specific class, is not natural. For example, "can this string be generated by a Turing machine on k states in n time".

Some things are less clear, like maybe linear programming, but I wouldn't worry too much about it. Study lots of algorithms and complexity problems and see if you agree with the general idea, or if you find examples that you think contradict it.

(In any case I think the "well-posed problem" route is definitely wrong by the way, as you suspect.)

---

[footnote] I don't mean to discourage you from trying to formalize it, just from thinking that you're meant to.

Answer 2

It roughly boils down to whether the problem definition could be circular:

• An artificial problem is one constructed to fill its class criteria.

• A natural problem does not rely on its method of construction to fill the class criteria.

Ladner's construction is known to be NP-intermediate, provided NPI exists.

Proving any candidate for NPI natural problems would prove $P \subsetneq NP$.

Caution: Good luck attempting to prove such a candidate; This may seem like an accessible approach but naturally has developed some barriers on proof.

Answer 3

I'm going to expand on the first possible answer. A natural transformation (WP, nLab) is, among many other things, a transformation (a k-transfor for some natural number k ≤ 1) which is natural in the systems which it transforms. Traditionally, the transformation goes from the "source" to the "target." (Those systems themselves are usually considered as lower-order transformations, but we'll elide that.) In particular, every instantiation of the source system with its varied parameters should be transformable to an instantiation of the target system, such that every collection of source parameters can also be transformed to a corresponding collection of target parameters.

Going deeper, in these notes on naturality, we are invited to consider isomorphisms and equivalences. In particular, our above transformation should also respect equivalences between systems; if a target system can be expressed in two different and equivalent ways, then the corresponding target parameters should also be isomorphic to their equivalents either way.

Note that, as a practical matter, natural transformations tend to feel somewhat hollow yet structured; the possibility to choose different systems tends to mean that the type of parameters is free, like an unbound variable.

We might therefore say that a natural computational problem is one which freely arises on some collection, rather than being about specific types like bits, bitstrings, or natural numbers.

For example, the problem of sorting a list is natural for any particular strict weak order, regardless of the underlying carrier. This is because any homomorphism of strict weak orders can be naturally lifted onto a sorting algorithm; just apply the homomorphism prior to sorting. In software engineering, this forms the basis of the Schwartzian transform, or decorate-sort-undecorate, where the homomorphism is chosen to replace the order structure of the strict weak order but preserve the original carrier.