Ответ от автора:
Читаем
http://www.cryptography.ru/db/msg.html?mid=1169815Там есть такой "абздец":
На вопрос о том, является ли задача факторизации $\mathrm{NP}$-полной, можно ответить коротко и чисто формально: безусловно, нет. Напомним, что \mathrm{NP} --- это класс языков, или, иначе, задач распознавания (decision problem). Задача факторизации --- это задача поиска решения (search problem) и она, по определению, не может принадлежать классу $\mathrm{NP}$. Но тем не менее, немного изменив подход, вопрос о $\mathrm{NP}$-полноте можно поставить вполне корректно. Например, вместо задачи поиска сомножителей можно рассматривать задачу распознавания языка $L=\{(N,i,\sigma)\}$, где $(N,i,\sigma)\in L$, если $N$ --- составное целое число и $i$-ый бит его максимального множителя равен $\sigma$. Очевидно, что задача факторизации и задача распознавания языка $L$ полиномиально эквивалентны. Альтернативно, можно рассматривать функциональные классы сложностей, состоящие из задач поиска решения. Например, задача ВЫПОЛНИМОСТЬ ставится так: дана булева формула, требуется найти набор знач
ений переменных, на котором эта формула принимает значение $1$. Функциональные аналоги классов сложностей, как правило, обозначают, добавляя букву F к соответствующему названию: $\mathrm{PF}$, $\mathrm{NPF}$ и т. п. Следует заметить, что соотношение между сложностью задач поиска решения и соответствующих задач распознавания представляет собой нетривиальную проблему. Ее исследование имеет большое значение для теории алгоритмов, теории сложности и математической криптографии. Но это --- тема для отдельного разговора.
Смотрите, как происходит введение ограничений и попадание на замыкание.
Прямо фраза за фразой с комментариями.
1. На вопрос о том, является ли задача факторизации $\mathrm{NP}$-полной, можно ответить коротко и чисто формально: безусловно, нет.
- Правильно! Факторизация чисел, которые принадлежат бесконечному множеству.
2. Задача факторизации --- это задача поиска решения (search problem) и она, по определению, не может принадлежать классу $\mathrm{NP}$.
- Абсолютно правильно!
3. Но тем не менее, немного изменив подход, вопрос о $\mathrm{NP}$-полноте можно поставить вполне корректно.
- Внимание! Идет подготовка к ошибке введения ограничений. Как в карточных
фокусах отвлекается внимание от самой ошибки подготовительными пасами.
4. Например, вместо задачи поиска сомножителей можно рассматривать задачу распознавания языка $L=\{(N,i,\sigma)\}$, где $(N,i,\sigma)\in L$, если $N$ --- составное целое число и $i$-ый бит его максимального множителя равен $\sigma$.
- Происходит подмена описания свойств бесконечного множества чисел на описание
свойств конечного множества алфавита языка. Т.е., делается попытка описать более
мощную систему высказываний для бесконечного множества чисел в терминах такой
же или менее мощной системы высказываний для конечного множества алфавита
языка. Явное противоречие теореме Гёделя "о замыкании". Вот она ошибка! Языки
с бесконечными алфавитами имеют другие свойства, нежели с конечными. Об этом
уже сказано выше в этой же статье.
5. Очевидно, что задача факторизации и задача распознавания языка $L$ полиномиально эквивалентны.
- Ошибка уже сделана. Получаем математический софизм, основанный на ошибке
замыкания (IDEM PER IDEM). Дальнейшие рассуждения будут основаны на ошибке,
не смотря на всю их внешнюю правдоподобность.
Глаз да глаз нужен за этими математиками!
Язык формальной математики менее мощный, чем Русский язык. Поэтому я и сделал
описание алгоритма на Русском языке. Чтобы избежать замыканий. Теперь, надеюсь,
и Реквием стал более понятен?
--
С уважением
Юрий
