- Problém
- Řešení
- Shrnutí
Pokud budete trávit čas v nebo kolem programování komunity, pravděpodobně jste slyšeli termín „P versus NP“ poměrně často. Bohužel i mnozí s formálním výcvikem v oblasti informatiky mají slabé pochopení tohoto konceptu.
takže zde je jednoduché a stručné vysvětlení:
problém
p vs. NP problém P vs. NP se ptá, zda každý problém, jehož řešení lze rychle ověřit počítačem, lze také rychle vyřešit počítačem., (Wikipedia)
takže pojďme zjistit, co máme na mysli P a NP.
p problémy jsou snadno vyřešeny počítači a problémy s NP nejsou snadno řešitelné, ale pokud předložíte potenciální řešení, je snadné ověřit, zda je správné nebo ne.
jak vidíte z výše uvedeného diagramu, všechny problémy s P jsou problémy s NP. To znamená, že pokud je pro počítač snadné vyřešit, je snadné ověřit řešení. Problém P vs NP se tedy jen ptá, zda jsou tyto dva typy problémů stejné nebo zda jsou odlišné, tj. že existují některé problémy, které lze snadno ověřit, ale nelze je snadno vyřešit.,
v současné době se zdá, že P ≠ NP, což znamená, že máme spoustu příkladů problémů, které můžeme rychle ověřit potenciální odpovědi, ale které nemůžeme vyřešit rychle. Pojďme se podívat na několik příkladů:
- obchodní cestující chce navštívit 100 různých městech jízdou, začíná a končí svou cestu na doma. Má omezenou zásobu benzínu, takže může řídit pouze celkem 10 000 kilometrů. Chce vědět, jestli může navštívit všechna města, aniž by mu došel benzín., (z Wikipedie)
- farmář chce na trh vzít 100 melounů různých mas. Potřebuje zabalit vodní melouny do krabic. Každá krabička může pojmout pouze 20 kilogramů bez rozbití. Zemědělec musí vědět, zda bude stačit 10 krabic, aby mohla nosit všech 100 vodních melounů na trh. (z Wikipedie)
Všechny tyto problémy mají společnou charakteristiku, která je klíčem k pochopení intrik P versus NP: V zájmu jejich vyřešení budete muset vyzkoušet všechny kombinace.
řešení
proto je odpověď na P vs., NP problém je pro lidi tak zajímavý. Pokud by někdo dokázal ukázat, že P se rovná NP, znamenalo by to pro počítače obtížné problémy v reálném světě triviální.
Shrnutí
- P vs. NP zabývá rozdíl mezi počítači je schopen rychle řešit problémy vs. jen byl schopen testovat navrhované řešení pro správnost.
- Jako takový, P vs. NP problém je hledání způsobu, jak řešit problémy, které vyžadují snahu o miliony, miliardy nebo biliony kombinací, aniž by ve skutečnosti museli vyzkoušet.,
- řešení tohoto problému by mělo hluboký dopad na výpočetní techniku, a tedy i na naši společnost.
Únor 7, 2017-přidána Wikipedia attributions.
Březen 2, 2014-vyčistil některé vysvětlení, aby nedošlo k záměně.