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:
“Ask me no more where Jove bestows,
When June is past, the fading rose;
For in your beauty’s orient deep
These flowers, as in their causes, sleep.
Ask me no more whither do stray
The golden atoms of the day;
For in pure love heaven did prepare
Those powders to enrich your hair.”
—Thomas Carew (1589–1639)
“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)
“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)