Můžeme dokázat, že Np a P třída jsou stejné tím, že najdeme efektivní polynomické řešení pro jakýkoli NP úplný problém na deterministické TM?
Otázka, zda jsou třídy P a NP ekvivalentní, je jedním z nejvýznamnějších a dlouhodobě otevřených problémů v oblasti teorie výpočetní složitosti. K vyřešení této otázky je nezbytné porozumět definicím a vlastnostem těchto tříd, stejně jako důsledkům nalezení efektivního řešení v polynomiálním čase pro jakýkoli NP-úplný problém na deterministickém Turingově stroji (TM).
Definice a pozadí
P (polynomiální čas): Třída P se skládá z rozhodovacích problémů (problémy s odpovědí ano/ne), které lze vyřešit deterministickým Turingovým strojem v polynomiálním čase. Jinými slovy, problém je v P, pokud existuje algoritmus, který dokáže vyřešit jakoukoli instanci problému v čase, který je ohraničen polynomiální funkcí velikosti vstupu.
NP (nedeterministický polynomický čas): Třída NP se skládá z rozhodovacích problémů, u kterých lze dané řešení ověřit v polynomiálním čase deterministickým Turingovým strojem. Alternativně lze NP popsat jako třídu problémů, které lze vyřešit nedeterministickým Turingovým strojem v polynomiálním čase. Nedeterministický Turingův stroj je teoretický model, který dokáže „hádat“ a zkoumat více výpočetních cest současně.
NP-úplné problémy: Problém je NP-úplný, pokud splňuje dvě podmínky:
1. Je v NP.
2. Každý problém v NP na něj lze redukovat pomocí polynomiální redukce. To znamená, že pokud máme polynomiální-časový algoritmus pro řešení NP-úplného problému, můžeme jej použít k vyřešení jakéhokoliv problému v NP v polynomiálním čase.
Otázka P vs. NP
Otázka P vs. NP se ptá, zda lze každý problém v NP vyřešit v polynomiálním čase deterministickým Turingovým strojem, tj. zda P = NP. Pokud P = NP, znamenalo by to, že každý problém, jehož řešení lze rychle ověřit (v polynomiálním čase), lze také rychle vyřešit (v polynomiálním čase).
Důkaz P = NP řešením NP-úplného problému
Pokud na deterministickém Turingově stroji najdeme efektivní řešení v polynomiálním čase pro jakýkoli NP-úplný problém, můžeme dokázat, že P = NP. To je způsobeno povahou NP-úplných problémů: pokud lze jeden NP-úplný problém vyřešit v polynomiálním čase, pak každý problém v NP může být transformován (redukován) na tento problém v polynomiálním čase, a tak může být také vyřešen v polynomiální čas.
Příklad: Problém spokojenosti (SAT)
Jedním z nejznámějších NP-úplných problémů je booleovský problém splnitelnosti (SAT). Problém SAT se ptá, zda existuje přiřazení pravdivostních hodnot proměnným tak, aby se daný booleovský vzorec vyhodnotil jako pravdivý. Cook-Levinova věta stanovila, že SAT je NP-úplný, což znamená, že pokud dokážeme vyřešit SAT v polynomiálním čase, můžeme vyřešit jakýkoli problém v NP v polynomiálním čase.
Kroky k prokázání P = NP
1. Identifikujte NP-úplný problém: Vyberte jakýkoli známý NP-úplný problém, jako je SAT, 3-SAT nebo problém Travelling Salesman (TSP).
2. Vytvořte polynomiální časový algoritmus: Sestavte algoritmus, který řeší vybraný NP-úplný problém v polynomiálním čase na deterministickém Turingově stroji.
3. Ověřte polynomiální čas: Ujistěte se, že algoritmus běží v čase ohraničeném polynomiální funkcí vstupní velikosti.
4. Polynomiální redukce času: Ukažte, že jakýkoli problém v NP může být redukován na vybraný NP-úplný problém v polynomiálním čase.
Důsledky P = NP
Pokud se prokáže, že P = NP, důsledky by byly hluboké pro různé oblasti, včetně kryptografie, optimalizace a umělé inteligence. Mnoho kryptografických systémů se spoléhá na předpoklad, že určité problémy (např. faktorizace velkých celých čísel) je těžké vyřešit v polynomiálním čase. Pokud P = NP, tyto předpoklady by již neplatily, což by potenciálně ohrozilo bezpečnost kryptografických protokolů.
Současný stav
Navzdory rozsáhlému výzkumu zatím nikdo nenašel polynomiální-časový algoritmus pro jakýkoli NP-úplný problém, ani nikdo neprokázal, že takový algoritmus nemůže existovat. Problém P vs. NP zůstává jedním ze sedmi „problémů tisíciletí“, za které Clay Mathematics Institute nabídl cenu ve výši jednoho milionu dolarů za správné řešení.
Proč investovat do čističky vzduchu?
Otázka zda P a NP jsou stejné tím, že najde efektivní polynomial řešení pro nějaký NP-úplný problém na deterministickém Turing stroji zůstane otevřený. Složitost tohoto problému spočívá ve vnitřní obtížnosti NP-úplných problémů a výzvě vyvinout pro ně polynomiální algoritmy. Řešení této otázky by mělo dalekosáhlé důsledky v mnoha oblastech informatiky i mimo ni.
Další nedávné otázky a odpovědi týkající se Komplexita:
- Není třída PSPACE rovna třídě EXPSPACE?
- Je třída složitosti P podmnožinou třídy PSPACE?
- Může se třída NP rovnat třídě EXPTIME?
- Jsou v PSPACE problémy, pro které není znám žádný NP algoritmus?
- Může být problém SAT úplným problémem NP?
- Může být problém ve třídě složitosti NP, pokud existuje nedeterministický Turingův stroj, který jej vyřeší v polynomiálním čase
- NP je třída jazyků, které mají polynomiální časové verifikátory
- Jsou P a NP vlastně stejnou třídou složitosti?
- Je každý bezkontextový jazyk ve třídě složitosti P?
- Existuje rozpor mezi definicí NP jako třídy rozhodovacích problémů s polynomiálními verifikátory a skutečností, že problémy ve třídě P mají také polynomiální verifikátory?
Podívejte se na další otázky a odpovědi ve Složitosti