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:
“Who knows whither the clouds have fled?
In the unscarred heaven they leave no wake,
And the eyes forget the tears they have shed,
The heart forgets its sorrow and ache;
The soul partakes the season’s youth,
And the sulphurous rifts of passion and woe
Lie deep ‘neath a silence pure and smooth,
Like burnt-out craters healed with snow.”
—James Russell Lowell (1819–1891)
“The Frenchman Jean-Paul ... Sartre I remember now was his last name had a dialectical mind good as a machine for cybernetics, immense in its way, he could peel a nuance like an onion, but he had no sense of evil, the anguish of God, and the possible existence of Satan.”
—Norman Mailer (b. 1923)
“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)