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:
“Poetry is a very complex art.... It is an art of pure sound bound in through an art of arbitrary and conventional symbols.”
—Ezra Pound (1885–1972)
“Man’s characteristic privilege is that the bond he accepts is not physical but moral; that is, social. He is governed not by a material environment brutally imposed on him, but by a conscience superior to his own, the superiority of which he feels. Because the greater, better part of his existence transcends the body, he escapes the body’s yoke, but is subject to that of society.”
—Emile Durkheim (1858–1917)
“A man’s women folk, whatever their outward show of respect for his merit and authority, always regard him secretly as an ass, and with something akin to pity. His most gaudy sayings and doings seldom deceive them; they see the actual man within, and know him for a shallow and pathetic fellow. In this fact, perhaps, lies one of the best proofs of feminine intelligence, or, as the common phrase makes it, feminine intuition.”
—H.L. (Henry Lewis)