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:
“The whole fauna of human fantasies, their marine vegetation, drifts and luxuriates in the dimly lit zones of human activity, as though plaiting thick tresses of darkness. Here, too, appear the lighthouses of the mind, with their outward resemblance to less pure symbols. The gateway to mystery swings open at the touch of human weakness and we have entered the realms of darkness. One false step, one slurred syllable together reveal a mans thoughts.”
—Louis Aragon (18971982)
“The light that radiates from the great novels time can never dim, for human existence is perpetually being forgotten by man and thus the novelists discoveries, however old they may be, will never cease to astonish.”
—Milan Kundera (b. 1929)
“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 (17111776)