Co je problém tisíciletí?
Otázka: Co je problém tisíciletí?
Odpověď: Problém tisíciletí je jedním z nejdůležitějších a nejnáročnějších matematických problémů tohoto století, který se zabývá otázkou, zda každý problém, který je pro počítače snadné ověřit, je také snadné vyřešit.
Otázka: Jak můžeme klasifikovat matematické problémy?
Odpověď: Matematické problémy lze klasifikovat jako problémy P nebo NP na základě toho, zda jsou řešitelné v konečném polynomiálním čase.
Otázka: Jaký je rozdíl mezi problémy P a NP?
Odpověď: Problémy P jsou pro počítače relativně rychlé a "snadné" k řešení, zatímco problémy NP jsou pro počítače rychlé a "snadné" ke kontrole, ale ne nutně snadno řešitelné.
Otázka: Kdo zavedl problém P versus NP?
O: Stephen Cook zavedl problém P versus NP v roce 1971 ve svém článku "The complexity of theorem proving procedures".
Otázka: Proč je problém P versus NP důležitý?
Odpověď: Problém P versus NP je považován za nejdůležitější otevřený problém v informatice a je jedním ze sedmi problémů Ceny tisíciletí, s cenou 1 000 000 dolarů za řešení, které vyvolá publikované uznání Clayova institutu a pravděpodobně takové(é), které změní celou matematiku.
Otázka: Je možné vyřešit NP-úplný problém v kvadratickém nebo lineárním čase?
Odpověď: V roce 1956 napsal Kurt Gödel dopis Johnu von Neumannovi, ve kterém se ptal, zda lze určitý NP-úplný problém vyřešit v kvadratickém nebo lineárním čase.
Otázka: Proč mnoho matematiků doufá, že problémy tisíciletí spolu souvisejí?
Odpověď: Mnoho problémů tisíciletí se dotýká souvisejících otázek a snem mnoha matematiků je vynalézt sjednocující teorie.
