| Тып файла | APK |
|---|---|
| Версія | 3.2.2 |
| Выдавец | Ofek Ron |
| Дата выпуску | 20 жні 2020 г. |
| Дата дададзена | 20 жні 2020 г. |
| Патрабаванні да ОС | Android |
| Патрабаванні | Requires Android 4.1 and up |
| Усяго загрузак | 0 |
| Кошт | Free |
Апісанне
Праблема P супраць NP з'яўляецца асноўнай нявырашанай праблемай у інфарматыцы. У ім абмяркоўваецца, ці можа кожная задача, рашэнне якой можа быць хутка праверана камп'ютэрам, таксама хутка вырашана камп'ютэрам. Гэта адна з сямі задач Прэміі тысячагоддзя, выбраных Інстытутам матэматыкі Клея, каб атрымаць прыз у 1 000 000 долараў ЗША за першае правільнае рашэнне. Праблема Гамільтанава цыкла - гэта добра вядомая NP-поўная задача з вобласці тэорыі графаў. Вырашэнне такой задачы, напрыклад, пошук паліномнага алгарытму, які вырашае яе пры любым зададзеным уваходным значэнні, наблізіла б чалавецтва як ніколі да вырашэння праблемы P супраць NP.
У гэтай гульні вам даецца графік, які ўяўляе сабой набор вузлоў і рэбраў, які часам утрымлівае гамільтанаў цыкл (даведацца больш тут https://en.wikipedia.org/wiki/Hamiltonian_path_problem), а часам не змяшчае, і вы трэба вырашыць, альбо выкрыўшы гамільтанаў цыкл, альбо вырашыўшы, што ён не існуе для гэтага графіка.
вялікую падказку па вызначэнні таго, ці з'яўляецца графік гамільтанавым (змяшчае цыкл Гамільтана), можна знайсці тут https://en.wikipedia.org/wiki/Graph_toughness.
Давайце і рашыце задачу на 1 мільён долараў і вывучайце тэорыю графаў!
