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:
“Came vested all in white, pure as her mind.
Her face was veiled; yet to my fancied sight
Love, sweetness, goodness, in her person shined
So clear as in no face with more delight.
But, O! as to embrace me she inclined,
I waked, she fled, and day brought back my night.”
—John Milton (1608–1674)
“We need not only a purpose in life to give meaning to our existence but also something to give meaning to our suffering. We need as much something to suffer for as something to live for.”
—Eric Hoffer (1902–1983)
“To invent without scruple a new principle to every new phenomenon, instead of adapting it to the old; to overload our hypothesis with a variety of this kind, are certain proofs that none of these principles is the just one, and that we only desire, by a number of falsehoods, to cover our ignorance of the truth.”
—David Hume (1711–1776)