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:
“If we parents accept that problems are an essential part of life’s challenges, rather than reacting to every problem as if something has gone wrong with universe that’s supposed to be perfect, we can demonstrate serenity and confidence in problem solving for our kids....By telling them that we know they have a problem and we know they can solve it, we can pass on a realistic attitude as well as empower our children with self-confidence and a sense of their own worth.”
—Barbara Coloroso (20th century)