| Failitüüp | APK |
|---|---|
| Versioon | 3.2.2 |
| Kirjastaja | Ofek Ron |
| Väljalaske kuupäev | 20. aug 2020 |
| Kuupäev lisatud | 20. aug 2020 |
| Os nõuded | Android |
| Nõuded | Requires Android 4.1 and up |
| Allalaadimisi kokku | 0 |
| Hind | Free |
Kirjeldus
P versus NP probleem on arvutiteaduses suur lahendamata probleem. Arutletakse selle üle, kas iga probleem, mille lahendust saab arvutiga kiiresti kontrollida, saab kiiresti ka arvutiga lahendada. See on üks seitsmest Clay Matemaatika Instituudi poolt valitud aastatuhande auhinnaülesannetest, mille esimese õige lahenduse eest antakse 1 000 000 USA dollari suurune auhind. Hamiltoni tsükli probleem on graafikuteooria valdkonnast hästi tuntud NP-täielik probleem. Sellise probleemi lahendamine, nt polünoomialgoritmi leidmine, mis selle mis tahes sisendis lahendab, muudaks inimkonna P versus NP probleemi lahendamisele lähemal kui kunagi varem.
Selles mängus antakse teile graafik, see on sõlmede ja servade komplekt, mis mõnikord sisaldab Hamiltoni tsüklit (lisateave siit https://en.wikipedia.org/wiki/Hamiltonian_path_problem) ja mõnikord mitte, ja teie tuleb see lahendada, paljastades Hamiltoni tsükli või otsustades, et seda selle graafiku jaoks ei eksisteeri.
Suure näpunäite selle otsustamiseks, kas graafik on hamiltoni (sisaldab Hamiltoni tsüklit), leiate siit https://en.wikipedia.org/wiki/Graph_toughness.
Lahendage 1 miljoni dollari suurune probleem ja õppige selle juures graafikuteooriat!
