Вопросы с тегом «pseudo-polynomial»

Почему бы не взять одинарное представление чисел в числовых алгоритмах?

Алгоритм псевдополиномиального времени - это алгоритм, который имеет полиномиальное время работы на входном значении (величина), но экспоненциальное время работы на входном размере (количество бит). Например, для проверки, является ли число простым или нет, требуется выполнить цикл по числам от 2...

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

Рассмотрим следующую постановку задачи: Получив начальное число, вы и ваш друг по очереди вычитаете из него идеальный квадрат. Первый, кто доберется до нуля, побеждает. Например: Начальное состояние: 37 Игрок1 вычитает 16. Состояние: 21 Игрок2 вычитает 8. Состояние: 13 Игрок1 вычитает 4. Состояние:...