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:
“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)