P (complexity) - Pure Existence Proofs of Polynomial-time Algorithms

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:

    Ask me no more where Jove bestows,
    When June is past, the fading rose;
    For in your beauty’s orient deep
    These flowers, as in their causes, sleep.

    Ask me no more whither do stray
    The golden atoms of the day;
    For in pure love heaven did prepare
    Those powders to enrich your hair.
    Thomas Carew (1589–1639)

    Question with boldness even the existence of a God; because, if there be one, he must more approve of the homage of reason, than that of blind-folded fear.
    Thomas Jefferson (1743–1826)

    To invent without scruple a new principle to every new phenomenon, instead of adapting it to the old; to overload our hypothesis with a variety of this kind, are certain proofs that none of these principles is the just one, and that we only desire, by a number of falsehoods, to cover our ignorance of the truth.
    David Hume (1711–1776)