I informatikk eksisterer det noen problemer hvis løsninger ennå ikke er funnet, problemene er delt inn i klasser kjent som Kompleksitetsklasser . I kompleksitetsteori er en kompleksitetsklasse et sett med problemer med relatert kompleksitet. Disse timene hjelper forskere til å gruppere problemer basert på hvor mye tid og plass de trenger for å løse problemer og verifisere løsningene. Det er grenen av beregningsteorien som omhandler ressursene som kreves for å løse et problem.

streng ti int

De vanlige ressursene er tid og rom, som betyr hvor mye tid algoritmen bruker på å løse et problem og tilhørende minnebruk.

• Tidskompleksiteten til en algoritme brukes til å beskrive antall trinn som kreves for å løse et problem, men den kan også brukes til å beskrive hvor lang tid det tar å bekrefte svaret.
• Plasskompleksiteten til en algoritme beskriver hvor mye minne som kreves for at algoritmen skal fungere.

Kompleksitetsklasser er nyttige for å organisere lignende typer problemer.

Typer kompleksitetsklasser

Denne artikkelen diskuterer følgende kompleksitetsklasser:

1. P klasse
2. NP klasse
3. CoNP klasse
4. NP-hardt
5. NP-komplett

P klasse

P-en i P-klassen står for Polynomtid. Det er samlingen av beslutningsproblemer (problemer med et ja eller nei svar) som kan løses av en deterministisk maskin i polynomisk tid.

Egenskaper:

• Løsningen til P problem s er lett å finne.
• P er ofte en klasse av beregningsproblemer som kan løses og løses. Tractable betyr at problemene kan løses i teorien så vel som i praksis. Men problemene som kan løses i teorien, men ikke i praksis, er kjent som uløselige.

Denne klassen inneholder mange problemer:

1. Beregner den største felles divisor.
2. Finne en maksimal matching.
3. Slå sammen sortering

NP klasse

NPen i NP-klassen står for Ikke-deterministisk polynomtid . Det er samlingen av beslutningsproblemer som kan løses av en ikke-deterministisk maskin i polynomisk tid.

bytte tilfelle java

Egenskaper:

• Løsningene til NP-klassen er vanskelige å finne siden de løses av en ikke-deterministisk maskin, men løsningene er enkle å verifisere.
• Problemer med NP kan verifiseres av en Turing-maskin i polynomisk tid.

Eksempel:

La oss vurdere et eksempel for bedre å forstå NP klasse . Anta at det er et selskap som har totalt 1000 ansatte har en unik medarbeider ID-er . Anta at det finnes 200 rom tilgjengelig for dem. Et utvalg av 200 ansatte må være sammenkoblet, men administrerende direktør i selskapet har dataene til noen ansatte som ikke kan jobbe i samme rom på grunn av personlige årsaker.
Dette er et eksempel på en F.eks problem. Siden det er lett å sjekke om det gitte valget av 200 ansatte foreslått av en medarbeider er tilfredsstillende eller ikke, det vil si at ingen par tatt fra medarbeiderlisten vises på listen gitt av administrerende direktør. Men å generere en slik liste fra bunnen av ser ut til å være så vanskelig at det er helt upraktisk.

Det indikerer at hvis noen kan gi oss løsningen på problemet, kan vi finne riktig og feil par i polynomisk tid. Altså for F.eks klasseproblem, er svaret mulig, som kan beregnes i polynomtid.

Denne klassen inneholder mange problemer som man ønsker å kunne løse effektivt:

1. Boolean Satisfiability Problem (SAT).
2. Hamiltonsk stiproblem.
3. Graffarging.

Co-NP klasse

Co-NP står for komplementet til NP Class. Det betyr at hvis svaret på et problem i Co-NP er Nei, så er det bevis som kan sjekkes i polynomtid.

Egenskaper:

• Hvis et problem X er i NP, er komplementet X' også i CoNP.
• For et NP- og CoNP-problem er det ikke nødvendig å verifisere alle svarene samtidig i polynomtid, det er behov for å bekrefte bare ett bestemt svar ja eller nei i polynomtid for at et problem skal være i NP eller CoNP.

Noen eksempler på problemer for CoNP er:

1. For å sjekke primtall.
2. Heltallsfaktorisering.

NP-hard klasse

Et NP-hardt problem er minst like vanskelig som det vanskeligste problemet i NP, og det er en klasse av problemer slik at hvert problem i NP reduseres til NP-hardt.

Egenskaper:

• Alle NP-harde problemer er ikke i NP.
• Det tar lang tid å sjekke dem. Dette betyr at hvis en løsning for et NP-hardt problem er gitt, tar det lang tid å sjekke om det er riktig eller ikke.
• Et problem A er i NP-hard hvis det for hvert problem L i NP eksisterer en polynomisk tidsreduksjon fra L til A.

Noen av eksemplene på problemer i Np-hard er:

les fra csv java

1. Stoppeproblem.
2. Kvalifiserte boolske formler.
3. Ingen Hamilton-syklus.

NP-komplett klasse

Et problem er NP-komplett hvis det er både NP og NP-hardt. NP-komplette problemer er de harde problemene i NP.

Egenskaper:

• NP-komplette problemer er spesielle ettersom ethvert problem i NP-klassen kan transformeres eller reduseres til NP-komplette problemer i polynomisk tid.
• Hvis man kunne løse et NP-komplett problem i polynomtid, så kunne man også løse et hvilket som helst NP-problem i polynomtid.

Noen eksempler på problemer inkluderer:

1. Hamiltonsk syklus.
2. Tilfredsstillelse.
3. Vertex deksel .