Disclaimer: Jag är för närvarande en student i en Data Science bootcamp, och vi har inte kommit in algoritmer ännu. Detta är bara något jag snubblat på medan du gör lite forskning på min egen tid. Jag tyckte det var ett intressant ämne. Definitivt inte ett proffs eller erfaren med algoritmer alls ännu. Förhoppningsvis kommer jag snart.
Från bara min grundläggande förståelse tror jag att dessa villkor alla handlar om Big-O-notation för algoritmer. Förhoppningsvis kan jag täcka detta på ett mycket förståeligt sätt.,
kort sammanfattning, Big-O är ett mått på hur snabbt en algoritm körs eller löser ett problem (notera att det är den övre gränsen för hur länge körtiden är).
P, NP, NP-Hard och NP-Complete är klasser som alla problem skulle falla under eller skulle klassificeras som.
p (polynom) problem
p problem hänvisar till problem där en algoritm skulle ta ett polynom tid att lösa, eller där Big-O är ett polynom (dvs O(1), O(n), O(n2), etc). Det här är problem som skulle anses vara ”lätta” att lösa, och har därför inte i allmänhet enorma körtider.,
NP (non-deterministic Polynomial) problem
NP problem var lite svårare för mig att förstå, men jag tror att det här är vad de är. När det gäller att lösa ett NP-problem skulle körtiden inte vara polynom. Det skulle vara något som O (n!) eller något mycket större. Denna typ av problem kan dock ges en specifik lösning, och kontroll av lösningen skulle ha en polynom run-time. Ett exempel som hjälpte mig att förstå detta lite bättre var ett Sudoku-spel.,
för att lösa hela detta pussel måste algoritmen kontrollera varje 3×3-matris för att se vilka nummer som saknas, sedan varje rad, sedan varje kolumn och se till att det inte finns några repetitioner av någon siffra från 0-9. Detta blir mer komplext eftersom antalet siffror som saknas är inkonsekvent i varje rad, kolumn och matris (dvs övre vänstra matrisen saknas 4 siffror medan övre högra matrisen saknas 8 siffror). Att lösa detta problem skulle inte ha en polynom run-time., Men om du skulle mata detta pussel med en möjlig lösning skulle det vara mycket mindre komplicerat att kontrollera om det finns några repetitioner i raderna, kolumnerna och matriserna. Detta är en enkel kontroll som skulle ha en polynom run-time.
i huvudsak har NP-klassproblem inte en polynomial körtid att lösa, men har en polynomial körtid för att verifiera lösningar (svårt att lösa, lätt att kontrollera ett visst svar).
reduktion
Jag kan inte riktigt förklara det här utanför att använda exempel, så: vi har två problem, A och B, och vi vet att problem B är ett p-klassproblem., Om problem a kan minskas eller konverteras till problem B, och denna minskning tar en polynom tid, kan vi säga att A också är ett p-klassproblem (A är reducerbar till B).
detta koncept är viktigt att förstå för de andra två klasserna av problem.
NP-hårda problem
ett problem klassificeras som NP-Hard när en algoritm för att lösa det kan översättas för att lösa alla NP-problem. Då kan vi säga att detta problem är minst lika svårt som något NP-problem, men det kan vara mycket svårare eller mer komplext.,
NP-kompletta problem
NP-kompletta problem är problem som lever i både NP och NP-hårda klasser. Detta innebär att NP-kompletta problem kan verifieras i polynom tid och att alla NP problem kan reduceras till detta problem i polynom tid.
nedan är ett venn-diagram över de olika klassrummen.,
<"7a9b3f049a" >
förhoppningsvis kunde detta ha rensat upp saker om detta ämne. Självklart har jag mycket begränsad kunskap. Jag tyckte bara att det var intressant att prata om och det verkar som, även på hög nivå, det här är ganska förvirrande.