Does the problem of P vs NP come under the category of Operational Research?

Question

I am enrolled in Operational Research program. Also interested in Algorithms, I wish to know whether P vs NP is a common point in both of the fields, so that the effort put in understanding this problem forwards me in both directions.

Answer 1

Yes, it comes up in OR (typically in references to problems being NP-complete or NP-hard). It is worth understanding, particularly in terms of understanding the limitations of what P versus NP versus not even NP (cannot be checked in polynomial time) means. The distinction is an asymptotic one (in terms of problem size).

Too many papers use "it's NP-hard" as a convenient excuse to whip out a metaheuristic ... regardless of what the actual solution time for an exact algorithm would be. For instance, it's convenient (and technically correct) to say that a traveling salesperson problem is NP-hard, but the Concorde solver has solved problems with close to 86,000 nodes. I've seen "it's NP-hard" used over and over as an excuse to apply a heuristic or metaheuristic to much smaller instances. So recognizing that "NP-hard" is not automatically a death sentence for exact methods is important in OR.

Answer 2

Linear programming is part of OR. In general, linear programming over the reals is in P, while integer linear programming (over the integers) is in NP.

Answer 3

No, the "P vs. NP" conjecture belongs to the Theory of Complexity.

Operational Research indeed consumes a lot of algorithms, some of which are in P, some not, but the key point is decision making, not discussing the relations between complexity classes. OR can be seen as an applied branch of Algorithmics.