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:
“We soon saw, as he saw, that he was not to be pardoned or rescued by men. That would have been to disarm him, to restore to him a material weapon, a Sharp’s rifle, when he had taken up the sword of the spirit,—the sword with which he has really won his greatest and most memorable victories. Now he has not laid aside the sword of the spirit, for he is pure spirit himself, and his sword is pure spirit also.”
—Henry David Thoreau (1817–1862)
“A more simple and natural man it would be hard to find. Vice and disease, which cast such a sombre moral hue over the world, seemed to have hardly any existence for him.”
—Henry David Thoreau (1817–1862)
“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)