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:
“Wilson adventured for the whole of the human race. Not as a servant, but as a champion. So pure was this motive, so unflecked with anything that his worst enemies could find, except the mildest and most excusable, a personal vanity, practically the minimum to be human, that in a sense his adventure is that of humanity itself. In Wilson, the whole of mankind breaks camp, sets out from home and wrestles with the universe and its gods.”
—William Bolitho (1890–1930)
“Realism holds that things known may continue to exist unaltered when they are not known, or that things may pass in and out of the cognitive relation without prejudice to their reality, or that the existence of a thing is not correlated with or dependent upon the fact that anybody experiences it, perceives it, conceives it, or is in any way aware of it.”
—William Pepperell Montague (1842–1910)
“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)