NP-полный вариант факторинга.

Книга Ароры и Барака представляет факторинг как следующую проблему:

$\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\}$

Далее в главе 2 добавляется, что устранение того факта, что $p$ простое, делает эту задачу NP-полной, хотя это не связано с трудностью факторизации чисел. Похоже, что может быть сокращение от SUBSETSUM, но я застрял, находя его. Удачи здесь лучше?

РЕДАКТИРОВАТЬ 1 марта: Награда предназначена для доказательства $NP$ полноты с использованием детерминированного сокращения Карпа (или Кука).

Это не совсем ответ, но это близко. Следующее является доказательством того, что задача NP-трудна при рандомизированных сокращениях.

Существует очевидная связь с суммой подмножества: предположим, вы знаете факторы : p 1 , p 2 , … , p k . Теперь вы хотите найти подмножество S из p 1 ... p k такое, что$N$$p_1$$p_2$$\ldots$$p_k$$S$$p_1$ $\ldots$ $p_k$

Проблема с попыткой использовать эту идею, чтобы показать, что проблема NP-трудна, состоит в том, что если у вас есть проблема с суммой подмножеств с числами , t 2 , … , t k , вы не можете обязательно найти простые числа за полиномиальное время, например что log p i ∝ t i (где под ∝ я подразумеваю приблизительно пропорционально). Это реальная проблема, потому что, поскольку subset-sum не является строго NP-полной, вам нужно найти эти log p i для больших целых чисел t $t_1$$t_2$$\ldots$$t_k$$\log p_i \propto t_i$$\propto$$\log p_i$$t_i$ .

Теперь предположим, что мы требуем, чтобы все целые числа … t k в задаче суммы подмножеств находились между x и x ( 1 + 1 / k ) , и чтобы сумма составляла приблизительно $t_1$ $\ldots$ $t_k$$x$$x(1+1/k)$. Проблема суммы подмножеств будет по-прежнему NP-полной, и любое решение будет суммойk/2целых чисел. Мы можем изменить задачу с целых чисел на действительные, если мы позволимt ′ i быть междуtiиti+$\frac{1}{2}\sum_i t_i$$k/2$$t'_i$$t_i$ , и вместо того, чтобы требовать, чтобы сумма была точноs, мы требуем, чтобы она была междуsиs+$t_i+\frac{1}{10k}$$s$$s$ . Нам нужно только указать наши числа примерно на4logkбольше битов, чтобы сделать это. Таким образом, если мы начнем с чисел сбитамиB, и мы можем указать действительные числаlogpiпримерно доB+4log$s + \frac{1}{10}$$4 \log k$$B$$\log p_i$$B + 4 \log k$ бит точности, мы можем осуществить наше сокращение.

Теперь из Википедии (через комментарий Сянь-Чжи ниже), число простых чисел между и Т + Т 5 / 8 является θ ( Т 5 / 8 / войти Т $T$$T+ T^{5/8}$$\theta(T^{5/8}/\log T)$ , так что если вы просто выбрать номера случайным образом в этом диапазоне, и проверить их на простоту, с высокой вероятностью получить штрих за полиномиальное время.

Теперь давайте попробуем сокращение. Допустим, все наши имеют длину B бит. Если мы возьмем T I длины 3 B биты, то можно найти простой р я вблизи Т я с 9 / 8 B битами точности. Таким образом, мы можем выбрать T i так, чтобы log T i ∝ t i с точностью 9 $t_i$$B$$T_i$$3B$$p_i$$T_i$$9/8B$$T_i$$\log T_i \propto t_i$ бит. Это позволяет нам найти p i ≈ T i, так что log p i ∝ t i с точностью 9 $9/8\, B$$p_i \approx T_i$$\log p_i \propto t_i$ бит. Если подмножество этих простых чисел умножается на что-то близкое к целевому значению, существует решение исходных проблем суммы подмножеств. Таким образом, мы позволяем N = Π i p i , выбираем L и U соответствующим образом, и мы получаем рандомизированное уменьшение от суммы подмножества.$9/8\,B$$N=\Pi_i p_i$$L$$U$

Я думаю, что это связано с теоремой PCP (в частности, ).$NP = PCP[O(\log{n}), O(1)]$

Отрывок из статьи Мадху :

... Идея о том, что верификатор может выполнять любые вычисления за полиномиальное время, значительно обогащает класс теорем и доказательств и начинает предлагать весьма нетривиальные методы доказательства теорем. (Одним из непосредственных следствий является то, что мы можем предположить, что теоремы / доказательства / утверждения / аргументы являются двоичными последовательностями, и мы будем делать это впредь.) Например, предположим, что у нас есть утверждение (скажем, гипотеза Римана), и скажем, что оно имеет доказательство, которое будет соответствовать статье в 10000 страниц. Вычислительная перспектива говорит, что с учетом A и этой границы (10 000 страниц) можно эффективно вычислить три натуральных числа N , L , U с L ≤ U ≤ $A$$A$$N, L, U$$L \leq U \leq N$таким образом, что истинно тогда и только тогда , когда N имеет делитель между L и U . Целые числа N , L и U будут довольно длинными (возможно, на их написание уйдет миллион страниц), но они могут быть созданы чрезвычайно эффективно (менее чем за то время, которое потребуется принтеру для распечатки всех этих целых чисел, что, конечно, самое большее день или два). (Этот конкретный пример основан на результате из-за личного общения Джо Килиана ) ...$A$$N$$L$$U$$N$$L$$U$

... далеко за пределы моих навыков теории сложности :-)

Это неформальная идея эффективного детерминированного сокращения (и может быть неполной):

Fractran - полный по Тьюрингу язык программирования. Соответствующим образом определяется ограниченно-версия программ Fractran должна быть приводимой к языку $\{\langle L, U, M \rangle \;|\; (\exists \text{ a positive integer } p \in \{L, \ldots, U\})[p | M]\}$

Например, ограниченная версия может спрашивать, производится ли целое число в выходной последовательности программы Fractran за определенное количество шагов (делений) (то есть M = N j ∗ F i ).$M$$M=N_j * F_i$