Чтобы понять это, вам нужно подумать о том, как время работы алгоритма изменяется с ростом размера чисел в наборе задач. Я предполагаю, что ваш учебник описывает обычную динамическую программную атаку на подмножество сумм. Время выполнения этого алгоритма растет линейно с шириной поставленной задачи. (Ширина набора проблем - это сумма положительных чисел в наборе минус сумма отрицательных чисел.) Эта ширина увеличивается в геометрической прогрессии при увеличении размера чисел в наборе. Например, если вы используете 101-битные числа вместо 100-битных, ширина поставленной задачи удваивается . Перейдите к 102-битным числам, и ширина набора проблем снова удвоится. А поскольку время выполнения алгоритма растет линейно с увеличением ширины набора задач, это время выполнения также удваивается каждый раз. Это удвоение является экспоненциальным ростом во время выполнения, поскольку размер входных данных увеличивается линейно, так что это не алгоритм за полиномиальное время.
Если бы числа были записаны в другой базе> 1, то да, вы бы увидели экспоненциальный рост ширины задачи в этой базе. Например, в базе 10 добавление еще одной цифры увеличивает ширину задачи в десять раз. Если вы переключитесь на унарный код, вы потеряете экспоненциальный рост размера набора задач, но вместо этого входной размер для любой заданной проблемы будет экспоненциально больше, чем в базах> 1, поэтому вы ничего не получите. 1011 *