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:
“Already nature is serving all those uses which science slowly derives on a much higher and grander scale to him that will be served by her. When the sunshine falls on the path of the poet, he enjoys all those pure benefits and pleasures which the arts slowly and partially realize from age to age. The winds which fan his cheek waft him the sum of that profit and happiness which their lagging inventions supply.”
—Henry David Thoreau (1817–1862)
“Sometimes I think that the biggest difference between men and women is that more men need to seek out some terrible lurking thing in existence and hurl themselves upon it.... Women know where it lives but they can let it alone.”
—Russell Hoban (b. 1925)
“Trifles light as air
Are to the jealous confirmation strong
As proofs of holy writ.”
—William Shakespeare (1564–1616)