Undflyende inom teorin om booleska funktioner

Sammanfattning

Aanderaa-Karp-Rosenberg f?rmodan ?r en f?rmodan ang?ende hur vissa egenskaper hos booleska funktioner relaterar till undflyende. ?ven om f?rmodan inte bevisats ?n har man lyckats visa att f?rmodan ”r sann om man antar vissa ytterligare krav p” funktionen. Denna uppsats kommer presentera den relevanta teorin kring f?rmodan samt simplicialtopologi som ett tillv?gag?ngss?tt att angripa problemet. F?rkunskaperna arbetet antar av l?saren ?r de som man l?r sig under de f?rsta tre ”ren p” matematikprogrammet. D?rav f?rv?ntas ingen kunskap inom grafteori samt endast grundl?ggande kunskap inom topologi och d?rmed kommer dessa ?mnen presenteras med detta i ?tanke. Efter den relevanta teorin presenterats kommer teorin till?mpas p? ett antal booleska funktioner i en resultatdel. Resultaten som presenteras kommer till st?rsta del best? av att visa att en boolesk funktion agerande p? en graf ?r undflyende eller icke-undflyende.