Докажите, что проблема факторинга α лежит в NP

Question

Пытаюсь освежить в памяти теорию вычислений, но я не уверен в ее решении:

Prove that the problem of factoring α is in NP.

У меня есть ощущение, что это может быть связано с обнаружением проблемы NP и поиском решения проблемы факторинга α.

Answer 1

Это на самом деле просто. Умножение в P. NP - это то же самое, что "проверка всех возможных решений полиномиального размера параллельно". Если альфа закодирована как длина n цепочки битов, общая длина факторов будет не более n + c.

То, что не является "NP-завершенным". Нет способа превратить произвольную проблему NP в факторинг.

Answer 2

Проблема в P : это проблема, которая вычисляется детерминированной машиной Тьюринга за полиномиальное время Проблема в NP : это проблема, так как она детерминирована с помощью детерминированной машины Тьюринга.

В NP мы используем недетерминизм таким образом, что нам требуется только одна ветвь дерева вычислений (мы пробуем «все» возможности в «одно и то же» время). Полиномиально очень надежный означает, что у нас есть сертификат (пусть это будет c), то есть решение для входного слова (пусть это будет w). Сертификат должен иметь полиномиальную длину с учетом входной длины. Наша задача - только проверить, является ли сертификат решением. Например, в SAT (проблема удовлетворяемости) сертификат является правильным присвоением (которое угадывается недетерминированно).

Итак, вы доказываете, что ваша проблема в NP: Существует DTM, который проверяет пару (w, c), где w - номер входа, а c - его факторы. Вы должны просто построить очень точное число, которое умножает множители на c и сравнивает его с w.