Uma variante NP-completa de fatoração.

45

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

FACTORING={L,U,N|( a prime p{L,,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

Michaël Cadilhac
fonte
5
@turkistany: FWIW, considero como estilo ruim colocar NP em itálico e como estilo ruim e LaTeX ruim para colocá-lo no modo matemático (pois o espaçamento entre as letras é diferente).
Michaël Cadilhac
@ Michaël, desculpe, voltou ao estilo original. Eu me animado com a sua pergunta :)
Mohammad Al-Turkistany
7
Uma descrição um pouco mais completa: Na página 63 do livro, eles escrevem: Alon e Kilian (em comunicação pessoal) mostraram que, na definição da linguagem Factoring no Exemplo 2.3, a condição de que o fator p é primo é necessária para capturar o problema de fatoração, uma vez que, sem essa condição, esse idioma é NP-completo (por razões que nada têm a ver com a dureza de fatorar números inteiros).
MS Dousti
2
Naturalmente, procurei um artigo de Alon e Kilian contendo “factoring” e “NP-complete”. Não encontrei nenhum (acho que isso também é natural em certo sentido). :(
Tsuyoshi Ito
5
@ Michael Na verdade, eu gosto de renderizar classes como vez de NP. Não ? NP
Suresh Venkat

Respostas:

35

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 1p k de modo queNp1p2pkSp1 pk

logLpiSlogpilogU.

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 .t1t2tklogpitilogpiti

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 1t1 tkxx(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+112itik/2titi , e em vez de exigir o montante a ser exatamenteé, exigimos que seja entreses+1ti+110kss . 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+1104logkBlogpiB+4logk

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.TT+T5/8θ(T5/8/logT)

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 / 8tiBTi3BpEuTEu9/8BTEuregistroTEutEu bits. Isso nos permite encontrar p iT i para que log p i alfa t i com precisão 9 / 89/8BpEuTEuregistropEutEu 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/8BN=ΠEupEueuvocê

Peter Shor
fonte
3
Eu não entendo a redução. Para que o problema da soma do subconjunto seja NP-completo, o número deve ser fornecido em binário. Se quisermos números inteiros cujos logaritmos estejam próximos dos números em uma instância do problema de soma de subconjuntos, precisaremos exponencialmente de muitos dígitos. Como você supera isso?
Tsuyoshi Ito
2
@ Peter: A suposição na teoria dos números é chamada de conjectura de Cramér , que afirma que , onde p n é o n-ésimo número primo. Consulte o artigo gap principal também para referência. pn+1pn=O(log2n)pn
Hsien-Chih Chang,
2
@ Peter: Sim, esta versão da suposição foi comprovada para grande o suficiente. O primeiro resultado deste tipo é mostrado por Hoheisel, e o melhor resultado devido a Wikipedia é o trabalho por Baker, Harman e Pintz , com α = 0,525 , c 1 = (uma vez que ele mantém para probabilidade 1) e c 2 = 1 . Tα=0,525c1=c2=1
Hsien-Chih Chang,
2
Apenas deparei com isso. Devo observar que não sei qual era a prova original de Kilian-Alon. Meu único conhecimento da prova é de uma comunicação com Noga que não se lembrava dos detalhes da prova original, e a prova que ele reconstruiu foi exatamente essa. Observe que também pode ser descrita como uma redução determinística sob algumas suposições teóricas de números fortes (por exemplo, que existe um primo em qualquer intervalo da forma [x, x + polylog (x)]).
precisa saber é o seguinte
4
Acabei de falar com Joe Kilian. Ele disse que a prova de que ele e Alon envolviam reduções aleatórias de erro zero. Tanto quanto ele sabe, a redução determinística ainda está aberta, a menos que você faça alguma suposição da teoria dos números, como Boaz Barak já disse.
Timothy Chow
8

Eu acho que está ligado ao teorema do PCP (em particular ).NP=PCP[O(registron),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 NUMAUMAN,eu,vocêeuvocêNde 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) ...UMANeuvocêNeuvocê

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

Marzio De Biasi
fonte
2
Esta é apenas outra formulação de que esse problema está completo como NP.
Marc Bury
@ Marc ... mmm ... Eu acho que isso significa: é NP-completo porque uma redução polinomial da NP-completo problemaPROVA DE CURTAexiste ...{eu,você,N|(p{eu,...,você})[p|N]}
Marzio De Biasi
2
O problema das PROVAS CURTAS no artigo é quase o mesmo que o problema de parada limitada. Uma redução do problema de CURTAS PROVAS seria provavelmente tão confusa quanto a prova típica da completude NP do SAT, e, portanto, é improvável que a prova da completude NP desse problema de encontrar fator por Kilian construa uma redução do PROVAS CURTAS problema diretamente.
Tsuyoshi Ito 03/03
0

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 {eu,você,M|( um número inteiro positivo p{eu,...,você})[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 jF i ).MM=NjFEu

Mohammad Al-Turkistany
fonte