Problems Not Known To Be P-complete
Some problems are not known to be either NP-hard or in P. These problems (e.g. factoring) are suspected to be difficult. Similarly there are problems that are not known to be either P-complete or NC, but are thought to be difficult to parallelize. Examples include the decision problem forms of finding the greatest common divisor of two numbers, and determining what answer the extended Euclidean algorithm would return when given two numbers.
Read more about this topic: P-complete
Famous quotes containing the word problems:
“The Settlement ... is an experimental effort to aid in the solution of the social and industrial problems which are engendered by the modern conditions of life in a great city. It insists that these problems are not confined to any one portion of the city. It is an attempt to relieve, at the same time, the overaccumulation at one end of society and the destitution at the other ...”
—Jane Addams (1860–1935)