Notable Problems in P
P is known to contain many natural problems, including the decision versions of linear programming, calculating the greatest common divisor, and finding a maximum matching. In 2002, it was shown that the problem of determining if a number is prime is in P. The related class of function problems is FP.
Several natural problems are complete for P, including st-connectivity (or reachability) on alternating graphs. The article on P-complete problems lists further relevant problems in P.
Read more about this topic: P (complexity)
Famous quotes containing the words notable and/or problems:
“Every notable advance in technique or organization has to be paid for, and in most cases the debit is more or less equivalent to the credit. Except of course when it’s more than equivalent, as it has been with universal education, for example, or wireless, or these damned aeroplanes. In which case, of course, your progress is a step backwards and downwards.”
—Aldous Huxley (1894–1963)
“There are nowadays professors of philosophy, but not philosophers. Yet it is admirable to profess because it was once admirable to live. To be a philosopher is not merely to have subtle thoughts, nor even to found a school, but so to love wisdom as to live according to its dictates, a life of simplicity, independence, magnanimity, and trust. It is to solve some of the problems of life, not only theoretically, but practically.”
—Henry David Thoreau (1817–1862)