Question

Всем привет! Заинтересовался одной задачей, решения в интернете НЕТ. Поэтому, если вы знаете, как её решить - решите, только, пожалуйста, объясните, как вы это сделали. Если вы не знаете, как её решать - не решайте. Хочу увидеть чёткий, адекватный ответ. Спасибо! Вот сама задача (кстати, не уверен, что её вообще можно решить, поэтому не обольщайтесь). Тема: комбинаторика.
Задача достаточно короткая: Для вычислительной машины, способной просчитать миллион игровых комбинаций в секунду с отсевом заведомо неоптимальных ветвей, на просчёт 6 ходов вперёд потребуется 1 секунда, на 12 ходов — 11 дней, а на 18 ходов — около 32000 лет. Вопрос: сколько лет потребуется этой самой вычислительной машине на то, чтобы просчитать 70 ходов? (Задача очень даже правдоподобна, под "игровыми комбинациями" подразумеваются шахматные комбинации. Спасибо!

Answer 1

Это задача относится к так называемым классом  $PH$ сложности   или просто  задача не решаемая за полинамиальное время , тем самым относится к категорий $NP=P$ классу , это значит что нет такого алгоритма  так что он решал бы данную задачу  при помощи скажем так рекурсивного метода , ИМЕННО метода ,потому что перебор идет " с отсевом заведомо неоптимальных ветвей"  , это видно из-за времени , на  просчитание ходов 
 Сама суть  задачи , на примере шахматной игры , или вообще какой-та  антагонистической игры  ,   когда вы играете с компьютером , он использует  так называемый принцип  Альфа-бета отсечение , то есть  к примеру вы сделали шаг  , и Компьютеру нужно некое время к примеру как в данной задачи (это не имеет значение)  $1$ - секунда      , вы делайте шаг , и теперь Компьютер оценивает ваш ход перебирая остальные  , и сужая тем самым последующие ходы в зависимости как вы пойдете в    следующий раз , то есть можно это изобразить в виде ГРАФА  ,  на который поставлены приоритеты в зависимости как вы ходили ,  компьютер описывает все действия при помощи некой функций  (но сам принцип , есть  оценивание этих самым ветвей графа), которое интерпретируется в сам процессоров в виде битов ,  вопрос  есть ли или существует алгоритм при помощи которой компьютер без проигрышна вас обыграет , то какой он 
 
 Явно выше сказанный алгоритм не без безпроигрышный , потому что  он только использует оценивание , после ваших ходов  то есть в любом случае оценивание , было бы хуже чем  в начале игры итд 
 
 Так в чем суть , полинамиальных классов задач , это в том что  , вы в зависимости от задачи , скажем так решаемой ,  описываете при помощи каких-то операций (алгоритма)  и он должен вывести , что задача не решается , то есть    зависимость $NP=P$  , то есть подставив ваши исходные данные  в псевдоокоде ,  есть ли он такой алгоритм который бы решал , данную задачу за некоторое время , ответ