Class Description

coRNC: Complement of RNC

Contains the problem of whether a bipartite graph has a perfect matching [Kar86].

Linked From

RNC: Randomized NC

Has the same relation to NC as RP does to P.

Contains the maximum matching problem for bipartite graphs [MVV87].

Contained in QNC.

See also: coRNC.

More about...