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.
5
-
1$\begingroup$ Just as I would not trust any civil engineer trying to build a bridge who did not understand differential equations, I would not trust any operations researcher trying to optimize a search algorithm who did not understand P vs. NP. $\endgroup$– Lee MosherAug 1, 2019 at 14:06
-
$\begingroup$ @LeeMosher, thank you for giving clarity, provides motivation for going ahead. $\endgroup$– Vikranth IntiAug 1, 2019 at 14:13
-
1$\begingroup$ What type of programme are you looking at? Is this a PhD? Masters? Undergraduate degree? Honours project? $\endgroup$– Theo BenditAug 1, 2019 at 14:13
-
$\begingroup$ @TheoBendit, I am registered as a student member for Post Graduate Diploma in O.R. at Operations Research Society of India. orsi.in The prospectus is here : orsi.in/pages/education/ORSI_Prospectus_latest.pdf $\endgroup$– Vikranth IntiAug 1, 2019 at 14:17
-
3$\begingroup$ X-posted: or.stackexchange.com/q/1132/8 $\endgroup$– Rodrigo de AzevedoAug 2, 2019 at 22:27
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
answered Aug 1, 2019 at 14:04