Hamilton for Android APK

Опис

Проблема P проти NP є основною невирішеною проблемою в інформатиці. У ній обговорюється, чи кожна проблема, рішення якої може бути швидко перевірено комп’ютером, також може бути швидко розв’язана комп’ютером. Це одна із семи завдань Премії тисячоліття, відібраних Інститутом математики Клея, щоб отримати премію в 1 000 000 доларів США за перше правильне рішення. Проблема Гамільтонового циклу є добре відомою NP-повною проблемою з теорії графів. Розв’язання такої проблеми, наприклад, знаходження поліноміального алгоритму, який розв’язує її за будь-якого вхідного сигналу, наблизило б людство ближче, ніж будь-коли, до вирішення проблеми P проти NP.

У цій грі вам надається графік, тобто набір вузлів і ребер, який іноді містить гамільтонів цикл (докладніше тут https://en.wikipedia.org/wiki/Hamiltonian_path_problem), а іноді ні, і ви потрібно розв’язати її, або розкривши гамільтонів цикл, або вирішивши, що він не існує для цього графіка.

Велику пораду щодо визначення того, чи є графік гамільтоновим (містить цикл Гамільтона), можна знайти тут https://en.wikipedia.org/wiki/Graph_toughness.

Розв’язуй задачу на 1 мільйон доларів і вивчай теорію графів!