Pure Existence Proofs of Polynomial-time Algorithms
Some problems are known to be solvable in polynomial-time, but no concrete algorithm is known for solving them. For example, the Robertson–Seymour theorem guarantees that there is a finite list of forbidden minors that characterizes (for example) the set of graphs that can be embedded on a torus; moreover, Robertson and Seymour showed that there is an O(n3) algorithm for determining whether a graph has a given graph as a minor. This yields a nonconstructive proof that there is a polynomial-time algorithm for determining if a given graph can be embedded on a torus, despite the fact that no concrete algorithm is known for this problem.
Read more about this topic: P (complexity)
Famous quotes containing the words pure, existence and/or proofs:
“I will use treatment to help the sick according to my ability and judgment, but never with a view to injury and wrongdoing. Neither will I administer a poison to anybody when asked to do so, nor will I suggest such a course. Similarly, I will not give to a woman a pessary to cause abortion. I will keep pure and holy both my life and my art.”
—Hippocrates (c. 460–c. 370 B.C.)
“Question with boldness even the existence of a God; because, if there be one, he must more approve of the homage of reason, than that of blind-folded fear.”
—Thomas Jefferson (1743–1826)
“I do not think that a Physician should be admitted into the College till he could bring proofs of his having cured, in his own person, at least four incurable distempers.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)