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 problems in p, notable and/or problems:
“I have a horror of people who speak about the beautiful. What is the beautiful? One must speak of problems in painting!”
—Pablo Picasso (1881–1973)
“In one notable instance, where the United States Army and a hundred years of persuasion failed, a highway has succeeded. The Seminole Indians surrendered to the Tamiami Trail. From the Everglades the remnants of this race emerged, soon after the trail was built, to set up their palm-thatched villages along the road and to hoist tribal flags as a lure to passing motorists.”
—For the State of Florida, U.S. public relief program (1935-1943)
“All problems are finally scientific problems.”
—George Bernard Shaw (1856–1950)