I am enrolled in an Operational Research program. I am also interested in Algorithms, and 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.
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ I can't help pointing to the traveling salesman movie. $\endgroup$– Marco LübbeckeAug 2, 2019 at 15:31
-
2$\begingroup$ X-posted: math.stackexchange.com/q/3310472/339790 $\endgroup$– Rodrigo de AzevedoAug 2, 2019 at 22:27
Add a comment
|
6 Answers
$\begingroup$
$\endgroup$
The short answer is yes, operations researchers care a lot about P vs NP. We deal in algorithms, and the complexity of those algorithms matters a lot to us.
The title of your question suggests you are asking whether P-vs-NP is contained within OR (although the body of your question does not). I would not say that P-vs-NP is contained within OR; rather, it is a topic that is of interest to operations researchers, computer scientists, mathematicians, and others.
answered Aug 2, 2019 at 15:15
$\begingroup$
$\endgroup$
P vs. NP may come "under" the category of Operational Research (O.R.). But unlike theoretical computer science and algorithm analysis, in which P vs. NP may be a be all and end all, practical (non-academic) O.R. people are not necessarily fixated on it.
In some circles, NP Hard is essentially considered to mean unsolvable. However, there are several commercial MILP (Mixed Integer Linear Programming) vendors whose entire business model is predicated on the ability and success of their customers to routinely solve NP Hard problems of practical business significance - that is O.R. in action.
answered Aug 2, 2019 at 15:33
$\begingroup$
$\endgroup$
This goes against the grain of the other answers here, but I do not believe that the P vs NP problem would naturally be categorized as a question in operations research. Instead, I would argue that it is a quintessential example of a question belonging to the TCS (theoretical computer science) field. As others have pointed out, a solution of the P vs NP problem would have potentially significant ramifications in OR, along with many other fields - including in the mathematical and physical sciences. It could even be the case that ultimately a solution of this problem arises from work that started out in OR, in which case it would be yet another example of techniques developed in one field solving a problem in another field.
Why do I hold this belief? Well, when people ask "what field does question X belong to?" they generally mean something along the lines of "which field did question X originate in? which field studies questions and lines of inquiry that naturally lead to question X? which field would experience the most significant influence due to a resolution of question X?" etc. etc. And the field of TCS meets all these criteria (in my opinion) for the P vs NP problem. For instance, wikipedia claims that the question was introduced in a paper entitled "The complexity of theorem proving procedures", presented at the Proceedings of the Third Annual ACM Symposium on Theory of Computing (emphasis mine).
While OR and TCS may have many overlapping areas of study and researchers, they are undoubtedly distinct fields (evidenced for example by the fact that I am writing this comment on the OR stackexchange and not the TCS stackexchange!)
$\begingroup$
$\endgroup$
While other answers have focused on the question whether "P vs. NP" can be considered to be in OR, I will instead look at the parts about this topic that I think are most relevant to study in the context of OR.
The basics
Before you can even properly understand what "$\mathsf{P}=\mathsf{NP}$" or "$\mathsf{P}\neq \mathsf{NP}$" means, you need to know what computational problems, complexity classes, and the classes $\mathsf{P}$ and $\mathsf{NP}$ are. Some algorithms textbooks include an explanation of the basics. this answer also provides a good introduction.1
Is my problem NP-hard?
The main practical application of the theory surrounding the P vs. NP question is that for many important computational problems for which no one has been able to find a polynomial-time algorithm, we can show that they are NP-hard. Proving that a problem is NP-hard provides a good argument that trying to find a polynomial-time algorithm for this problem is futile.
Does this mean that once we have shown a problem is NP-hard, we should give up on this problem?
Beyond NP-hardness
No, of course not. We should give up on finding an exact polynomial-time algorithm and look at other algorithms instead.
There are other types of algorithms with theoretical performance and quality guarantees: e.g. approximation algorithms, exact exponential algorithms, and fixed parameter tractable (FPT) algorithms. There are general frameworks that can be used to describe NP-hard problems and highly optimized solvers that can often find optimal solutions within reasonable time: e.g. ILP-solvers, SAT-solvers, and constraint satisfaction solvers. We can also choose not to provide guarantees on the solution quality or performance at all and try to find heuristics that work well in practice.
Many problems of interest within OR are NP-hard (e.g. scheduling, TSP), yet there are plenty of algorithms within the frameworks mentioned above that can find solutions to these hard problems that can be used in practice.
This is, in my opinion, why the P vs. NP question is relevant for OR. It is not the answer to the question: that will probably elude us for a long time and is very likely not to come from OR. Also, whether it is within the context of OR that the question was originally asked is debatable. What is relevant for OR is the fact that this question has remained unresolved for years. This justifies looking beyond NP-hardness to get actual solutions, which is what a large part of OR has been doing.
1: A completely formal treatment of this topics requires diving into computational models such as Turing machines, but I do not think that is nessecary to use the concepts in "guiding" algorithm design
$\begingroup$
$\endgroup$
As mentioned by others, OR is definitely involved in the P vs. NP issue. If you can find a polynomial time algorithm to solve the Quadratic Assignment Problem or the TSP which Marco mentioned, both of which are essentially OR problems, then you can say P = NP.
But, the P vs. NP issue is not strictly “under” OR because there are other fields which are closely intertwined with the “debate” (pure math, applied math, computer science).
$\begingroup$
$\endgroup$
The other answers are good. I'd add that "P vs. NP" spans OR, CS, project management, education, HR, governance, and several other related fields. Procedures, algorithms, project and business plans, software, curricula, legislation, and other forms of code are hard to prove correct without actually executing them to see what happens. The execution may be NP-hard or even undecidable, but due in part to e.g. the halting problem and its cousins we seldom can know ahead of time.
This very practical and day-to-day OR-class problem hits organizations all the time; few understand or deal with it well. One symptom of this is lengthy project plans that stack all of the testing towards the end. Another is logistics systems with long queues where testing happens on exit from the queue instead of on entry. Staffing practices which revolve around an annual review along with infrequent formal training or certification are another. The worst are the mega-projects which rely on an untested architecture set in stone years before an immovable completion date.
Practitioners who do tend to get things right are those who break the problem up into smaller chunks and then iterate, test, and refactor rapidly in response to intermediate results. You'll see implementations of this in lean manufacturing, war/scenario gaming, agile and test driven software development, devops, US military training, the "fail fast" ethos in startups, and so on.
