| Тип файла | 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 миллион долларов, а заодно изучай теорию графов!
