Komplexitetsteori
Innehåll- 1. Allmänt - 2. Problemklasser - 3. Reduktion1. Allmänt
Komplexitetsteori behandlar hur resurskrävande lösandet av olika beräkningsproblem är under olika förutsättningar. Resurserna man resonerar om är i regel tidsåtgång eller minnesåtgång.2. Problemklasser
Inom komplexitetsteorin delar man in problem i klasser efter gemensamma egenskaper. De två klasserna som torde vara mest kända är P och NP, eftersom de dels innehåller många vanliga problem och dels eftersom det är en öppen fråga om de är lika. Klasserna består av problem lösbara i polynomisk tid med en deterministisk resp. ickedeterministisk Turingmaskin.3. Reduktion
Reduktion innebär att man med någon metod kan omformulera ett problem till ett annat, och på så sätt visa på egenskaper hos det första problemet.Ett exempel: Vi har det okända problemet A och ett känt problem B som är i klassen P. Om vi lyckas visa att vi med någon polynomisk metod kan översätta alla probleminstanser i A till probleminstanser i B, så har vi visat att vi kan lösa alla probleminstanser i A i polynomisk tid (tid för översättningen + tiden för att lösa B-problemet), och därmed har vi visat att A också är i P.
Artikeln skriven 2009-01-16 av Learning4sharing
Inga kategorier för denna artikel än...Intresserad av fler artiklar?
Litterat programmeringRolf Skoglund
Webproxy
Malena Ernman
Skillnaden mellan Plopp samt Center
Kapsyl
Gynnare
PTSD
Axel Nilsson Banér