Leírás
A matroidelmélet egyik központi eredménye Edmonds tétele, mely karakterizálciót ad két matroid maximális közös független halmazának a méretére. A tétel segítségével az is eldönthető, hogy két matroidnak van-e közös bázisa. Edmonds és Fulkerson választ adott arra a szorosan kapcsolódó problémára is, mely során egyetlen matroidban keresünk k diszjunkt bázist.
A két feladat közös általánosítása, mely során két matroid metszetében szeretnénk k közös bázist pakolni, ezidáig nyitott volt. Az előadáson belátjuk, hogy a probléma nehéz: nem oldható meg polinomiális sok függetlenségi orákulum hívással. Azt is megmutatjuk, hogy a NAE-SAT feladat speciális esete a közös bázisok pakolásának, így az absztrakt matroidelméleti probléma NP-teljes speciális eseteket is magában foglal. A bizonyítás egyben azt is mutatja, hogy a feladat már abban az igen speciális esetben is nehéz, amikor k=2, az egyik matroid partíciós, a másik matroid pedig explicit lineáris reprezentációval adott.