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 very existence of government at all, infers inequality. The citizen who is preferred to office becomes the superior to those who are not, so long as he is the repository of power, and the child inherits the wealth of the parent as a controlling law of society.”
—James Fenimore Cooper (1789–1851)
“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)