P versus NP – zatím nevyřešená otázka z výpočetní techniky. Představme si, že jsme nějak uhodli řešení problému a počítač dokáže polynomiálním algoritmem ověřit, že jde o řešení. Existuje také polynomiální algoritmus, kterým počítač toto řešení sám nalezne? Problém byl zformulován v roce 1971 a řešení není dodnes známo. P třída: polynomiální ověření, polynomiální řešení. NP třída: polynomiální ověření, nepolynomiální řešení. Platí P = NP? Tj. existuje i pro NP úlohy polynomiální algoritmus řešení?

Zpět  Glosář

---