Hemtal 2 i Algoritmer och komplexitet 1995

Hemtalet ska lösas enskilt, dvs helt utan samarbete. Följ hederskodexen som finns i kursprogrammet!
Lämna dina lösningar skriftligt till Viggo senast måndag den 8 maj klockan 12 (men tidigare inlämning går också bra). I detta hemtal måste du motivera att dina reduktioner och argument är riktiga.
Lösningen ska också redovisas muntligt under veckan 8-12 maj. Bokning av redovisningstid görs med kommandot bok new algokomp95 på Nadas unixdatorer. Kommandot bok help ger mer information om detta.
Fullständigt korrekt lösning ger 3 bonuspoäng på tentan. För att få bonuspoäng på hemtalet måste du redovisa både skriftligt och muntligt.

Uppgifter

  1. Inom mobiltelefonin behöver man lösa frekvensallokeringsproblemet som lyder på följande sätt. Det finns ett antal sändare utplacerade. Varje sändare kan sända på någon av en given uppsättning frekvenser. Olika sändare kan ha olika frekvensuppsättningar. Vissa sändare är så nära varandra att dom inte kan sända på samma frekvens, för då skulle dom störa varandra. (Detta beror faktiskt inte så mycket på avståndet som på geografin - om det finns något berg, hus eller liknande som skärmar av.)
    Man vet från början vilka sändare som finns, vilken frekvensuppsättning varje sändare har och vilka par av sändare som skulle störa varandra om dom sände på samma frekvens. Problemet är att avgöra ifall det finns något möjligt val av frekvenser så att inte någon sändare stör någon annan.

    Formulera detta problem som ett grafproblem och visa att det är NP-fullständigt!

  2. Det är välkänt att INDEPENDENT SET (problemet att givet en graf G och ett tal k avgöra huruvida det finns k hörn i G som inte har någon kant mellan sej) är NP-fullständigt. Eftersom problemet SAT (satisfierbarhet av en boolesk formel) är NP-fullständigt vet vi därför att det existerar en reduktion (i polynomisk tid) från INDEPENDENT SET till SAT. Detta beror på att varje NP-problem kan lösas i polynomisk tid av en ickedeterministisk turingmaskin och varje sånt problem kan enligt Cooks sats beskrivas med en boolesk formel.

    Konstruera en direkt reduktion från INDEPENDENT SET till SAT, dvs konstruera en reduktion som går i polynomisk tid och som inte bygger på Cooks sats!

    Ledning: Det svåra är faktiskt att uttrycka jämförelsen med k som en boolesk formel. För att lyckas med det kan man införa booleska variabler som numrerar dom hörn som ingår i den oberoende mängden, dvs som håller reda på vilket nummer från 1 till k hörnet har i den oberoende mängden.

^ Upp till aktuella kurssidan.


Senast ändrad 1995-03-29 <viggo@nada.kth.se>