Влияние числовой базы при доказательстве NP полноты численных задач - PullRequest
1 голос
/ 11 декабря 2011

Я читаю о полноте NP из книги проектирования алгоритмов tardos. В разделе доказательства сумма подмножества NP завершена, написано, что -
Алгоритм, разработанный для суммы подмножеств, имеет время работы O (нВт). Если задан экземпляр из 100 чисел, каждое из которых имеет длину 100 битов, то на входе будет только 100 * 100 = 10000 цифр, но W примерно 2 ^ 100.
Я не понимаю это утверждение, почему W 2 ^ 100? Каково влияние базы на эту проблему, я имею в виду, если мы изменим ее на какую-то другую базу x, будет ли W x ^ 100? что если мы изменим его в унарную базу?
спасибо.

1 Ответ

0 голосов
/ 04 января 2012

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

Если бы числа были записаны в другой базе> 1, то да, вы бы увидели экспоненциальный рост ширины задачи в этой базе. Например, в базе 10 добавление еще одной цифры увеличивает ширину задачи в десять раз. Если вы переключитесь на унарный код, вы потеряете экспоненциальный рост размера набора задач, но вместо этого входной размер для любой заданной проблемы будет экспоненциально больше, чем в базах> 1, поэтому вы ничего не получите. 1011 *

...