Inom datavetenskap finns det några problem vars lösningar ännu inte hittats, problemen är indelade i klasser som kallas Komplexitetsklasser . Inom komplexitetsteorin är en komplexitetsklass en uppsättning problem med relaterad komplexitet. Dessa klasser hjälper forskare att gruppera problem baserat på hur mycket tid och utrymme de behöver för att lösa problem och verifiera lösningarna. Det är grenen av beräkningsteorin som handlar om de resurser som krävs för att lösa ett problem.

tecken till sträng

De vanliga resurserna är tid och rum, vilket betyder hur mycket tid algoritmen tar för att lösa ett problem och motsvarande minnesanvändning.

• Tidskomplexiteten för en algoritm används för att beskriva antalet steg som krävs för att lösa ett problem, men den kan också användas för att beskriva hur lång tid det tar att verifiera svaret.
• Rymdkomplexiteten hos en algoritm beskriver hur mycket minne som krävs för att algoritmen ska fungera.

Komplexitetsklasser är användbara för att organisera liknande typer av problem.

Typer av komplexitetsklasser

Den här artikeln diskuterar följande komplexitetsklasser:

1. P klass
2. NP-klass
3. CoNP-klass
4. NP-hårt
5. NP-komplett

P klass

P:et i P-klassen står för Polynomtid. Det är samlingen av beslutsproblem (problem med ett ja eller nej svar) som kan lösas med en deterministisk maskin i polynomtid.

Funktioner:

• Lösningen till P problem s är lätt att hitta.
• P är ofta en klass av beräkningsproblem som är lösbara och lösbara. Tractable innebär att problemen kan lösas i teorin såväl som i praktiken. Men de problem som kan lösas i teorin men inte i praktiken är kända som svårlösta.

Den här klassen innehåller många problem:

1. Beräknar den största gemensamma divisorn.
2. Hitta en maximal matchning.
3. Sammanfoga sortering

NP-klass

NP i NP-klass står för Icke-deterministisk polynomtid . Det är samlingen av beslutsproblem som kan lösas av en icke-deterministisk maskin i polynomtid.

Funktioner:

operativ system

• Lösningarna för NP-klassen är svåra att hitta eftersom de löses av en icke-deterministisk maskin men lösningarna är lätta att verifiera.
• Problem med NP kan verifieras av en Turing-maskin i polynomtid.

Exempel:

Låt oss överväga ett exempel för att bättre förstå NP klass . Anta att det finns ett företag som har totalt 1000 anställda som har unika medarbetare ID:n . Anta att det finns 200 tillgängliga rum för dem. Ett urval av 200 anställda måste paras ihop, men företagets VD har uppgifter om vissa anställda som inte kan arbeta i samma rum på grund av personliga skäl.
Detta är ett exempel på en T.EX problem. Eftersom det är lätt att kontrollera om det givna valet av 200 anställda som föreslås av en medarbetare är tillfredsställande eller inte, dvs inget par som tagits från medarbetarlistan förekommer på den lista som ges av VD. Men att skapa en sådan lista från början verkar vara så svårt att det är helt opraktiskt.

Det indikerar att om någon kan ge oss lösningen på problemet, kan vi hitta det korrekta och felaktiga paret i polynomtid. Alltså för T.EX klassproblem, är svaret möjligt, vilket kan beräknas i polynomtid.

Denna klass innehåller många problem som man skulle vilja kunna lösa effektivt:

1. Boolean Satisfiability Problem (SAT).
2. Hamiltons vägproblem.
3. Graffärgning.

Co-NP klass

Co-NP står för komplementet till NP Class. Det betyder att om svaret på ett problem i Co-NP är Nej, så finns det bevis som kan kontrolleras i polynomtid.

Funktioner:

• Om ett problem X är i NP, är dess komplement X' också i CoNP.
• För ett NP- och CoNP-problem finns det inget behov av att verifiera alla svar på en gång i polynomtid, det finns ett behov av att endast verifiera ett specifikt svar ja eller nej i polynomtid för att ett problem ska vara i NP eller CoNP.

Några exempel på problem för CoNP är:

1. För att kontrollera primtal.
2. Heltalsfaktorisering.

NP-hård klass

Ett NP-hårt problem är minst lika svårt som det svåraste problemet i NP och det är en klass av problem så att varje problem i NP reduceras till NP-hårt.

sträng jämför med java

Funktioner:

• Alla NP-hårda problem finns inte i NP.
• Det tar lång tid att kontrollera dem. Detta innebär att om en lösning för ett NP-hårt problem ges så tar det lång tid att kontrollera om det är rätt eller inte.
• Ett problem A är i NP-hårt om det för varje problem L i NP finns en polynom-tidsreduktion från L till A.

Några av exemplen på problem i Np-hard är:

1. Stoppa problem.
2. Kvalificerade booleska formler.
3. Ingen Hamilton-cykel.

NP-komplett klass

Ett problem är NP-komplett om det är både NP och NP-hårt. NP-kompletta problem är de svåra problemen i NP.

Funktioner:

• NP-kompletta problem är speciella eftersom alla problem i NP-klass kan transformeras eller reduceras till NP-kompletta problem i polynomtid.
• Om man kunde lösa ett NP-komplett problem i polynomtid, så skulle man också kunna lösa vilket NP-problem som helst i polynomtid.

Några exempel på problem inkluderar:

1. Hamiltons cykel.
2. Tillfredsställelse.
3. Vertex lock .