Может ли это быть проблемой NP-Complete?

10

Рассмотрим следующую постановку задачи:

Получив начальное число, вы и ваш друг по очереди вычитаете из него идеальный квадрат. Первый, кто доберется до нуля, побеждает. Например:

Начальное состояние: 37

Игрок1 вычитает 16. Состояние: 21

Игрок2 вычитает 8. Состояние: 13

Игрок1 вычитает 4. Состояние: 9

Player2 вычитает 9. Состояние: 0

Player2 выигрывает!

Напишите программу, которая при заданном начальном состоянии возвращает оптимальный ход, то есть тот, который гарантированно приведет к победе в игре. Если никакое возможное движение не может привести вас к выигрышному состоянию, верните -1.

Эта проблема может быть решена в псевдополиномиальное время с помощью динамического программирования. Идея состоит в том, чтобы просто заполнить массив длиной n (где n - начальное состояние) снизу оптимальными ходами или -1, если ни один ход не приводит к победе. Это заняло бы O (n * sqrt (n)), так как для каждого числа мы должны рассмотреть вычитание каждого возможного совершенного квадрата, меньшего его (их есть ~ sqrt (n)). Однако это псевдополиномиальная сложность среды выполнения, поскольку среда выполнения фактически экспоненциально масштабируется по отношению к размеру входных данных в двоичном формате (число битов, используемых для представления числа).

Кто-нибудь может придумать полиномиальный алгоритм для решения этой проблемы? Если нет, то может ли это быть NP-Complete? Почему?

complexity-theory time-complexity np-complete dynamic-programming pseudo-polynomial Мартин Копес
источник
1
Из любопытства, почему вы специально спрашиваете, является ли он NP-завершенным? (Лично я бы предположил, что это даже не в NP, хотя я действительно не знаю.)
ruakh
@ruakh Недавно я столкнулся с этой проблемой во время интервью по кодированию и предложил псевдополиномиальное решение с использованием динамического программирования, которое я описал. Однако, тщательно подумав о проблеме, я не смог придумать алгоритм полиномиального времени. Вскоре я начал задавать себе вопрос, не является ли это на самом деле проблемой NP (-Полной).
Мартин
Вы пытались вычислить, какие позиции являются выигрышными, а какие проигрывают? Возможно, возникнет закономерность.
Юваль
@YuvalFilmus Согласно Википедии, не существует известной формулы для этого шаблона (последовательность A030193 в OEIS)
Мартин
Хорошо, я просто собирался опубликовать ответ с этой информацией. Смотрите также A224839.
Юваль

Ответы:

6

Последовательность проигрышных позиций может быть найдена в OEIS, A030193 , так же как и последовательность позиций, имеющих значение Grundy 1, A224839 . Энциклопедия цитирует несколько соответствующих статей. Возможно, некоторые из них обсуждают нетривиальные алгоритмы вычисления последовательности.

Юваль Фильмус
источник
Как вы упомянули, эта последовательность представляет проигрышные позиции. Даже если вы смогли в постоянное время проверить, теряет ли позиция или нет (что кажется трудным!), Проблема все равно просит вас вернуть оптимальное движение, то есть, какую клетку вам нужно вычесть до текущего состояния, чтобы добраться до проигрышная позиция. Проблема сводится к поиску проигрышной позиции путем вычитания квадратов из текущего состояния. Таким образом, вам все еще нужно перебирать все квадраты, меньшие, чем состояние, даже если вы можете проверить, проигрывает ли позиция в постоянном времени.
Мартин
3
Да, этого будет недостаточно, но это будет хорошим началом. Возможно, вы получите некоторое представление о том, как рассчитать только выигрышный статус позиции. Кроме того, показа того, что трудно решить, какую позицию проигрывать, будет достаточно, чтобы показать, что ваша проблема, как указано, является NP-трудной, в любой разумной версии решения.
Юваль