In Stephen Cook's paper on the P vs NP problem, he states the following :
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." 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 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", says he will conduct "a literal discussion what is a natural problem". At the close of the paper, 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", 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.
- "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
- p. 3
- p. 4
- 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.
- p. 2.
- p. 47-8, section 25