Uma variante NP-completa de fatoração.

O livro de Arora e Barak apresenta o fatorial como o seguinte problema:

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

Eles acrescentam, ainda no capítulo 2, que remover o fato de ser primo torna esse problema NP completo, embora isso não esteja relacionado à dificuldade de fatorar números. Parece que pode haver uma redução do SUBSETSUM, mas fiquei preso ao encontrá-lo. Alguma sorte por aqui?$p$

Edição 1º de março: A recompensa é para a prova de completude do usando a redução determinística de Karp (ou Cook).$NP$

Esta não é uma resposta, mas está perto. A seguir, é uma prova de que o problema é NP-difícil sob reduções aleatórias.

Existe uma relação óbvia com a soma do subconjunto, que é: suponha que você conheça os fatores de : p 1 , p 2 , ... , p k . Agora, você deseja encontrar um subconjunto S de p 1 … p k de modo que$N$$p_1$$p_2$$\ldots$$p_k$$S$$p_1$ $\ldots$ $p_k$

O problema com a tentativa de usar essa idéia para mostrar o problema é NP-hard é que se você tem um problema de soma subconjunto com números , t 2 , ... , t k , você pode não necessariamente encontrar números primos em tempo polinomial, tais que log p i ct t i (onde por α , quer dizer, aproximadamente, proporcional ao). Este é um problema real, porque, uma vez subconjunto de soma não é fortemente NP-completo, você precisa encontrar estes log p i para grandes inteiros t i .$t_1$$t_2$$\ldots$$t_k$$\log p_i \propto t_i$$\propto$$\log p_i$$t_i$

Agora, suponha que exigem que todos os inteiros ... t k em um subconjunto problema da soma estão entre x e x ( 1 + 1 / k ) , e que a soma é de aproximadamente $t_1$ $\ldots$ $t_k$$x$$x(1+1/k)$. O problema da soma do subconjunto ainda será NP-complete e qualquer solução será a soma dosk/2inteiros. Nós podemos mudar o problema de números inteiros para reais se deixarmost ' i estar entretieti+$\frac{1}{2}\sum_i t_i$$k/2$$t'_i$$t_i$ , e em vez de exigir o montante a ser exatamenteé, exigimos que seja entreses+$t_i+\frac{1}{10k}$$s$$s$ . Só precisamos especificar nossos números com cerca de4logkbits de precisão para fazer isso. Assim, se começamos com números combitsBe podemos especificar números reaislogpipara aproximadamenteB+4logkbits de precisão, podemos realizar nossa redução.$s + \frac{1}{10}$$4 \log k$$B$$\log p_i$$B + 4 \log k$

Agora, a partir wikipedia (via comentário de Hsien-Chih abaixo), o número de primos entre e T + T 5 / 8 é θ ( T 5 / 8 / log T ) , então se você basta escolher números aleatoriamente nesse intervalo, e testá-los quanto à primalidade, com alta probabilidade de obter um primo em tempo polinomial.$T$$T+ T^{5/8}$$\theta(T^{5/8}/\log T)$

Agora, vamos tentar a redução. Digamos que o nosso são todos B bits de comprimento. Se tomarmos T i de comprimento 3 B pedaços, então podemos encontrar um número primo p i perto T i com 9 / 8 B bits de precisão. Assim, podemos escolher T i para que log T i alfa t i com precisão 9 /$t_i$$B$$T_i$$3B$$p_i$$T_i$$9/8B$$T_i$$\log T_i \propto t_i$ bits. Isso nos permite encontrar p i ≈ T i para que log p i alfa t i com precisão 9 /$9/8\, B$$p_i \approx T_i$$\log p_i \propto t_i$ bits. Se um subconjunto desses primos se multiplica para algo próximo ao valor alvo, existe uma solução para os problemas de soma do subconjunto original. Por isso, deixe N = Π i p i , escolher G e L de forma adequada, e que tem uma redução randomizado de soma subconjunto.$9/8\,B$$N=\Pi_i p_i$$L$$U$

Eu acho que está ligado ao teorema do PCP (em particular ).$NP = PCP[O(\log{n}), O(1)]$

Um trecho do artigo de Madhu :

... A noção de que um verificador pode executar qualquer cálculo de tempo polinomial enriquece consideravelmente a classe de teoremas e provas e começa a oferecer métodos altamente não triviais de provar teoremas. (Uma conseqüência imediata é que podemos assumir que teoremas / provas / asserções / argumentos são seqüências binárias e o faremos a partir de agora.) Por exemplo, suponha que tenhamos uma asserção (digamos a Hipótese de Riemann) e digamos que acreditamos que ela tenha prova que caberia em um artigo de 10.000 páginas. A perspectiva computacional diz que, dado A e esse limite (10.000 páginas), é possível calcular com eficiência três números inteiros positivos N , L , U com L ≤ U ≤ $A$$A$$N, L, U$$L \leq U \leq N$de tal modo que é verdadeiro se e apenas se N tem um divisor entre L e L . Os números N , L e U serão muito longos (talvez seja necessário escrevê-los em um milhão de páginas), mas eles podem ser produzidos com extrema eficiência (em menos do que o tempo que uma impressora levaria para imprimir todos esses números inteiros, que é certamente no máximo um dia ou dois). (Este exemplo específico é baseado em um resultado devido a Joe Kilian , comunicação pessoal) ...$A$$N$$L$$U$$N$$L$$U$

... muito além das minhas habilidades em teoria da complexidade :-)

Esta é uma ideia informal de redução determinística eficiente (e pode estar incompleta):

Fractran é uma linguagem de programação completa de Turing. A limitada versão adequadamente definido de programas Fractran deve ser redutível à linguagem $\{\langle L, U, M \rangle \;|\; (\exists \text{ a positive integer } p \in \{L, \ldots, U\})[p | M]\}$

Por exemplo, uma versão limitada poderia perguntar se o número inteiro é produzido na sequência de saída de um programa Fractran dentro de um certo número de etapas (divisões) (isto é, M = N j ∗ F i ).$M$$M=N_j * F_i$