Problems in NC
As with P, by a slight abuse of language, one might classify function problems and search problems as being in NC. NC is known to include many problems, including
- Integer addition, multiplication and division;
- Matrix multiplication, determinant, inverse, rank;
- Polynomial GCD, by a reduction to linear algebra using Sylvester matrix (it is open whether integer GCD is in NC);
- Finding a maximal matching.
Often algorithms for those problems had to be separately invented and could not be naïvely adapted from well-known algorithms – Gaussian elimination and Euclidean algorithm rely on operations performed in sequence. One might contrast ripple carry adder with a carry-lookahead adder.
Read more about this topic: NC (complexity)
Famous quotes containing the word problems:
“Currently, U.S. society has been encouraged by its political and subsidized mass-media intelligentsia to view U.S. life as a continual “morning in America” paradise, where the only social problems occur in the inner cities. Psychologists call this denial.”
—Ishmael Reed (b. 1938)