Как узнать, занимает ли алгоритм псевдополиномиальное время??

Получив вопрос, я пытаюсь его решить и предполагаю, что нашел алгоритм.

Предполагается.

Теперь я делаю анализ временной сложности для этого алгоритма и обнаруживаю, что он работает за полиномиальное время.

Полиномиальное время относительно чего? Числовое значение ввода или длина кодировки этого значения?

Теперь как я могу убедиться, что мой алгоритм работает только за полиномиальное, а не за псевдополиномиальное время?

Алгоритм работает за полиномиальное время, если время работы ограничено полиномиальной функцией длины кодирования входных данных. Он псевдополиномиальный, если время его выполнения ограничено полиномиальной функцией значения входных данных, когда оно интерпретируется как число.

Или просто я могу поставить свой вопрос так: есть ли способ узнать, требует ли алгоритм псевдополиномиального времени?

Будьте осторожны с тем, вычисляете ли вы сложность w.r.t. значение ввода или длина представления ввода на компьютере (не имеет значения, является ли компьютер реальным физическим компьютером или концептуальным компьютером).

function isPrime(n):
    for i from 2 to n - 1:
        if (n mod i) = 0, return false
    return true

Мы думаем, что приведенное выше решение работает за полиномиальное время, но на самом деле это решение имеет псевдополиномиальную сложность.

Время выполнения этой функции ограничено полиномиальной функцией от n и экспоненциальной функцией от длины кодирования ввода.

Ключом к определению ответа является понимание того, что, хотя ввод равен n, входной размер равен log_2(n) (на компьютерах, которые представляют числа в двоичном виде).