China
Africa
Explore chapters and articles related to this topic
Introduction to Operations Research
Published in Michael W. Carter, Camille C. Price, Ghaith Rabadi, Operations Research, 2018
Michael W. Carter, Camille C. Price, Ghaith Rabadi
It is known that P ⊆ NP, but it is an open question whether P = NP. In other words, are the NP-complete problems truly more costly to solve than the problems in P, or have analysts just not yet been clever enough to discover efficient algorithms for these apparently difficult problems? Discovery of an efficient (polynomial-time) algorithm for any NP-complete problem would be sufficient to establish that P = NP and, therefore, that all the NP-complete problems can be solved efficiently. In the absence of any such discovery, analysts are faced daily with the need to solve practical problems that are computationally intractable. Chapter 10 reveals how some of these problems are dealt with in effective and affordable ways. An informative overview of this subject is available in Garey and Johnson (1979).
Use of Metaheuristics in Reverse Logistics and De-manufacturing
Published in Eren Özceylan, Surendra M. Gupta, Sustainable Production and Logistics, 2021
Seamus M. McGovern, Surendra M. Gupta
Though it is suspected that NP-complete problems are intractable (where a problem cannot be solved by any known polynomial-time algorithm), this has never been proven or disproved. Once determined and proven, the answer to the question “is P = NP?” will affect every problem that is NP-complete. If and when answered, it will be known that no NP-complete problem will ever be solved in polynomial time or that all NP-complete problems can be optimally solved.
The exact complexity of the Tutte polynomial
Published in Joanna A. Ellis-Monaghan, Iain Moffatt, Handbook of the Tutte Polynomial and Related Topics, 2022
Tomer Kotek, Johann A. Makowsky
We denote by NP the set of decision problems for which it is possible to verify whether a given configuration is correct in polynomial time in the size of the input. We denote by ♯P (pronounced “number P” or “sharp P”) the set of counting problems which count configurations whose correctness can be verified in polynomial time. For example the problem of deciding whether a graph is r-colorable is in NP, and computing the number of r-colorings is in ♯P. Whether P=NP and whether FP=♯P are famous and notoriously difficult open questions in theoretical computer science. A problem X is NP -hard (respectively, ♯P -hard) if using it as an oracle allows one to solve any problem in NP (respectively in ♯P) in polynomial time. Problems which are NP-hard (or ♯P -hard) are provably the hardest problems in NP (respectively ♯P), and are are considered intractable. They are not considered effectively computable, unless NP=P, respectively ♯P=FP.
Medical diagnosis and treatment is NP-complete
Published in Journal of Experimental & Theoretical Artificial Intelligence, 2021
Jeffrey. E. Arle, Kristen W. Carlson
Problems that are NP and NP-hard are NP-complete (NPC), a remarkable class in that all NPC problems, while often appearing very different from each other, have a related underlying structure, since they can be mapped to each other in PTIME (Arora & Barak, 2009; Sipser, 2006). Thousands of important mathematical and real-world problems have been shown to be NPC. The P class can be thought of as including those problems for which programmers have found efficient algorithms to solve them, while NPC contains those for which even the greatest programmers have not yet succeeded in finding a solution algorithm (Garey & Johnson, 1979). The great P = NP mystery is whether, with more cleverness and perseverance, we can find an algorithm to solve any NPC problem in PTIME – recall they appear to require computational resources that grow in super-polynomial time. If such an algorithm can be found, even in one single case, then all NPC problems would be solvable in PTIME, saving inestimable computational resources (Arora & Barak, 2009; Hopcroft & Ullman, 1979; Sipser, 2006). To wit, recently a problem tackled by leading mathematicians and computer science for decades, suspected of being intrinsically intractable, was shown to be polynomial-time tractable with a simple 2-page proof (Huang, 2019). No one knows whether showing that P = NP may be close at hand, impossible to prove, or false.