V informatice existují některé problémy, jejichž řešení dosud nebyla nalezena, problémy jsou rozděleny do tříd tzv Třídy složitosti . V teorii složitosti je třída složitosti souborem problémů se související složitostí. Tyto třídy pomáhají vědcům seskupit problémy podle toho, kolik času a prostoru potřebují k řešení problémů a ověření řešení. Je to odvětví teorie počítání, které se zabývá zdroji potřebnými k vyřešení problému.

co je awt

Společnými zdroji jsou čas a prostor, což znamená, kolik času algoritmu zabere vyřešení problému a odpovídající využití paměti.

• Časová složitost algoritmu se používá k popisu počtu kroků potřebných k vyřešení problému, ale může být také použita k popisu toho, jak dlouho trvá ověření odpovědi.
• Prostorová složitost algoritmu popisuje, kolik paměti je potřeba pro fungování algoritmu.

Třídy složitosti jsou užitečné při organizování podobných typů problémů.

Typy tříd složitosti

Tento článek pojednává o následujících třídách složitosti:

1. Třída P
2. Třída NP
3. Třída CoNP
4. NP-tvrdý
5. NP-kompletní

Třída P

P ve třídě P znamená Polynomiální čas. Je to soubor rozhodovacích problémů (problémy s odpovědí ano nebo ne), které lze vyřešit deterministickým strojem v polynomiálním čase.

Funkce:

• Řešení k P problém s je snadné najít.
• P je často třídou výpočetních problémů, které jsou řešitelné a řešitelné. Řešitelný znamená, že problémy lze řešit teoreticky i prakticky. Ale problémy, které lze vyřešit teoreticky, ale ne v praxi, jsou známé jako neřešitelné.

Tato třída obsahuje mnoho problémů:

1. Výpočet největšího společného dělitele.
2. Nalezení maximální shody.
3. Sloučit třídění

Třída NP

NP ve třídě NP znamená Nedeterministický polynomický čas . Je to soubor rozhodovacích problémů, které lze vyřešit nedeterministickým strojem v polynomiálním čase.

Funkce:

• Řešení třídy NP je těžké najít, protože je řeší nedeterministický stroj, ale řešení lze snadno ověřit.
• Problémy NP lze ověřit Turingovým strojem v polynomiálním čase.

Příklad:

Podívejme se na příklad pro lepší pochopení třída NP . Předpokládejme, že existuje společnost, která má celkem 1000 zaměstnanci mají jedinečného zaměstnance ID . Předpokládejme, že existují 200 pokoje pro ně k dispozici. Výběr z 200 zaměstnanci musí být spárováni, ale generální ředitel společnosti má k dispozici údaje některých zaměstnanců, kteří nemohou z osobních důvodů pracovat ve stejné místnosti.
Toto je příklad an NAPŘ problém. Vzhledem k tomu, že je snadné zkontrolovat, zda je daná volba 200 zaměstnanci navržení spolupracovníkem jsou uspokojiví nebo ne, tj. žádný pár převzatý ze seznamu spolupracovníků se neobjeví na seznamu poskytnutém generálním ředitelem. Ale generování takového seznamu od začátku se zdá být tak těžké, že je zcela nepraktické.

prohlášení bash if

Znamená to, že pokud nám někdo může poskytnout řešení problému, můžeme najít správnou a nesprávnou dvojici v polynomiálním čase. Tedy pro NAPŘ třídní problém, odpověď je možná, kterou lze vypočítat v polynomiálním čase.

Tato třída obsahuje mnoho problémů, které by člověk chtěl umět efektivně řešit:

1. Booleovský problém uspokojitelnosti (SAT).
2. Problém hamiltonovské cesty.
3. Barvení grafu.

Třída Co-NP

Co-NP znamená doplněk třídy NP. To znamená, že pokud je odpověď na problém v Co-NP Ne, pak existuje důkaz, který lze zkontrolovat v polynomiálním čase.

Funkce:

• Pokud je problém X v NP, pak jeho doplněk X‘ je také v CoNP.
• U problému NP a CoNP není potřeba ověřovat všechny odpovědi najednou v polynomiálním čase, je potřeba ověřit pouze jednu konkrétní odpověď ano nebo ne v polynomiálním čase, aby byl problém v NP nebo CoNP.

Některé příklady problémů pro CoNP jsou:

1. Pro kontrolu prvočísla.
2. Faktorizace celých čísel.

NP-těžká třída

NP-těžký problém je přinejmenším stejně těžký jako nejtěžší problém v NP a je to třída problémů, takže každý problém v NP se redukuje na NP-těžký.

Funkce:

• Všechny NP-těžké problémy nejsou v NP.
• Jejich kontrola trvá dlouho. To znamená, že pokud je dáno řešení pro NP-těžký problém, pak trvá dlouho, než se ověří, zda je správné nebo ne.
• Problém A je v NP-těžký, pokud pro každý problém L v NP existuje polynomiální časová redukce z L na A.

Některé příklady problémů v Np-hard jsou:

1. Problém se zastavením.
2. Kvalifikované booleovské vzorce.
3. Žádný hamiltonovský cyklus.

NP-úplná třída

Problém je NP-úplný, pokud je NP i NP-těžký. NP-úplné problémy jsou těžké problémy v NP.

r v jazyce c

Funkce:

• NP-úplné problémy jsou speciální, protože jakýkoli problém ve třídě NP lze transformovat nebo redukovat na NP-úplné problémy v polynomiálním čase.
• Pokud bychom mohli vyřešit NP-úplný problém v polynomiálním čase, pak bychom mohli také vyřešit jakýkoli NP problém v polynomiálním čase.

Některé příklady problémů:

1. Hamiltonovský cyklus.
2. Spokojenost.
3. Vertexový kryt .