Undflyende inom teorin om booleska funktioner
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.