Perfect Matching ist NL-hart

Описание: Das Problem "Perfect Matching" ist die Frage, ob ein gegebener ungerichteter Graph ein perfektes Matching besitzt, das ist eine Menge paarweise disjunkter Kanten, die alle Knoten abdecken. Wir zeigen durch eine Reduktion von STCON (Erreichbarkeit in gerichteten Graphen), dass Perfect Matching NL-hart ist, sogar für bipartite Graphen.

0:00 Definition von (Bipartite) Perfect Matching
4:35 Reduktion
12:32 Die wahre Komplexität von Perfect Matching?