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:
“A bad end, a sad end, was the last end of Mieze. And why, why, why? What crime had she committed? She came from Bernau into the whirl of Berlin, she was not an innocent girl, certainly not, but her love for him was pure and steadfast; he was her man and she took care of him like a child. She was struck down because she happened by chance to encounter this man; such is life, it’s really inconceivable.”
—Alfred Döblin (1878–1957)
“The individual who has to justify his existence by his own efforts is in eternal bondage to himself.”
—Eric Hoffer (1902–1983)
“Would you convey my compliments to the purist who reads your proofs and tell him or her that I write in a sort of broken-down patois which is something like the way a Swiss waiter talks, and that when I split an infinitive, God damn it, I split it so it will stay split, and when I interrupt the velvety smoothness of my more or less literate syntax with a few sudden words of bar- room vernacular, that is done with the eyes wide open and the mind relaxed but attentive.”
—Raymond Chandler (1888–1959)