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:
“Teenage girls are extremists who see the world in black-and- white terms, missing shades of gray. Life is either marvelous or not worth living. School is either pure torment or is going fantastically. Other people are either great or horrible, and they themselves are wonderful or pathetic failures. One day a girl will refer to herself as “the goddess of social life” and the next day she’ll regret that she’s the “ultimate in nerdosity.””
—Mary Pipher (20th century)
“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)
“I do not think that a Physician should be admitted into the College till he could bring proofs of his having cured, in his own person, at least four incurable distempers.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)