Escrever um número como dois quadrados e escrever os fatores de um número são igualmente difíceis?

Seja e o seguinte: $L_1$ $L_2$

$L_1=\{r:\exists x,y \in \mathbb{Z} \text{ such that } x^2+y^2=r\}$

$L_2=\{(N,M): M<N, \exists 1<d\leq M \text{ such that d|N} \}$

Reivindicar $L_1 \leq_P L_2$

Prova de esboço

Se eu quero saber se . $r\in L_1$

O número de soluções inteiras para é dado por $x^2+y^2=r$

$g(r)=\sum_{d|r}{\chi{(d)}}$ que $\chi (x)=sin(\frac{\pi x}{2})=\cases{ 1\text{ when }x\cong 1 \text{ mod }4 \\ -1 \text{ when }x\cong 3 \text{ mod }4 \\ 0 \text{ when } 2|x }$

Então . Então, responder é " ?" é tão difícil de responder quanto "quais são os divisores de ?" $L_1=\{r: g(r)\neq 0\}$ $r\in L_1$ $r$

$\square$

O que eu gostaria de saber é se isso é verdade ao contrário. É verdade que se eu tivesse uma máquina que pudesse me informar em tempo constante se poderia criar uma máquina que pudesse responder "é ?" em tempo polinomial? $r\in L_1$ $(M,N)\in L_2$

Motivações

Esta questão surgiu de uma discussão sobre esta questão .

Desculpas Sou realmente apenas um membro do math.se que se perdeu e vagou para o cs.se. Informe-me se minha pergunta estiver clara e dentro dos padrões deste site. Fico feliz em fazer correções.

complexity-theory time-complexity np decision-problem Pedreiro
fonte

Estou usando corretamente?

\leq_{P}

$\leq_P$

Mason

Sua redução está correta, mas sua conclusão de que é "tão difícil quanto" está incorreta. Você acabou de mostrar que é no máximo tão difícil quanto . Especificamente, você realmente mostra que é no máximo tão difícil quanto um caso muito restrito de , o que pode ser muito fácil.

L_{1} \leq_{p} L_{2}

$L_1\le_p L_2$

L_{1}

$L_1$

L_{2}

$L_2$

L_{1}

$L_1$

L_{2}

$L_2$

L_{1}

$L_1$

L_{2}

$L_2$

Shaull

Em vez de "satisfazer um círculo", um termo melhor poderia ser "ser uma soma de dois quadrados".

Yuval Filmus

@ Shaull, mudei um idioma para refletir seu comentário.

Mason

Computar é de fato conhecido por ser tão difícil quanto fatorar, até uma redução de tempo polinomial aleatória. Veja Bach, Miller e Shallit: soma de divisores, números perfeitos e fatoração .

\sum_{d ∣ n} d

$\sum_{d\mid n}d$

Emil Jerabek

Respostas:

Aqui está a situação, tanto quanto eu posso dizer:

A maneira mais eficiente conhecida para testar a associação em é fatorar . Nenhum algoritmo mais eficiente parece ser conhecido. $L_1$ $r$

No entanto, não há redução óbvia para provar . Em outras palavras, se tivéssemos uma máquina para decidir , não há uma maneira fácil de usar isso para fatorar. Se queremos levar um número , podemos verificar se , mas isso só nos dá um pouco de informação sobre os fatores de . Testar múltiplos de (isto é, se para algum número inteiro ) não nos fornece nenhuma informação adicional, pois saber se é suficiente para prever se para todos $L_2 \le_P L_1$ $L_1$ $N$ $N \in L_1$ $N$ $N$ $cN \in L_1$ $c$ $N \in L_1$ $cN \in L_1$ $c>0$ . Testar outros números também não parece ajudar de maneira óbvia. (Testar se para outro número parece não fornecer informações úteis, se ; e se tivéssemos uma maneira de encontrar outro número modo que , já sabíamos como fatorar, mas é claro que não sabemos como fazer isso - portanto, qualquer número que sabemos gerar é improvável que nos dê alguma utilidade informações sobre os fatores de ) Esta não é uma prova; é apenas intuição ondulada. $N' \in L_1$ $N'$ $\gcd(N,N') =1$ $N'$ $\gcd(N,N')\ne 1$ $N$

Portanto, parece plausível que possa ser mais fácil que , e também parece plausível que possam ter a mesma dificuldade. Não estou ciente de mais resultados sobre esse assunto. $L_1$ $L_2$

DW
fonte