Menu
I encountered many problems that can be formulated as graph problem. It is in general NP-hard but sometimes the graph can be proved to be planar. Hence, I am interested in learning these problems and the algorithms.
So far as I know:
Hope someone can complete this list.
393
Nobody has yet been able to determine conclusively whether NP-complete problems are in fact solvable in polynomial time, making this one of the great unsolved problems of mathematics.
(i) All NP-complete problems are solvable in polynomial time: Yes. Every problem in NP is polynomially reducible to SAT, and SAT is reducible to every NP-hard problem. Therefore, a polynomial time solution to any NP-hard problem (such as 3Col) implies that every problem in NP can be solved in polynomial time.
P-Class. The class P consists of those problems that are solvable in polynomial time, i.e. these problems can be solved in time O(nk) in worst-case, where k is constant. These problems are called tractable, while others are called intractable or superpolynomial.
NP-complete problems are the hardest problems in the NP set. A decision problem L is NP-complete if: 1) L is in NP (Any given solution for NP-complete problems can be verified quickly, but there is no efficient known solution).
In this compendium of NP-complete problems, under planar in the index there are a good number (~25) of entries. These entries typically link to problems where planar input admits a PTAS.
99
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
