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.