Comprovando a (in) tratabilidade desta enésima recorrência principal

18

Como se segue da minha pergunta anterior , tenho brincado com a hipótese de Riemann como uma questão de matemática recreativa. No processo, cheguei a uma recorrência bastante interessante e estou curioso quanto ao nome, suas reduções e sua tratabilidade em direção à resolubilidade da diferença entre os números primos.

Em termos gerais, podemos definir a diferença entre cada número primo como uma recorrência dos primos candidatos anteriores . Por exemplo, para nossa base de , o próximo primo seria:p0=2

p1=min{x>p0cos(2π(x+1)/p0)+1=0)}

Ou, como vemos ao traçar isso : p1=3 .

Podemos repetir o processo para primos avaliando cada candidato a cada candidato recorrente. Suponha que queremos obter o próximo primo, . Nossa função candidata se torna:p 2np2

p2=min{x>p1fp1(x)+((cos(2π(x+1)/p1)+1)(cos(2π(x+2)/p1)+1))=0}

Onde:

fp1(x)=cos(2π(x+1)/p0)+1 , como acima.

É fácil ver que cada função de componente se torna zero em valores inteiros e é igualmente fácil mostrar como isso captura inteligentemente nossos relacionamentos em forma de AND e XOR, explorando as propriedades de adição e multiplicação no contexto de um sistema trigonométrico. equações

A recorrência se torna:

fp0=0p0=2fpn(x)=fpn1(x)+k=2pn1(cos(2π(x+k1)/pn1)+1)pn=min{x>pn1fpn(x)=0}

... onde todo o problema depende da capacidade de avaliar o operador min nessa função em tempo polinomial. Esta é, de fato, uma generalização da Peneira de Eratóstenes .

Trabalhando código Python para demonstrar a recorrência:

from math import cos,pi

def cosProduct(x,p):
    """ Handles the cosine product in a handy single function """
    ret = 1.0
    for k in xrange(2,p+1):
        ret *= -cos(2*pi*(x+k-1)/p)+1.0
    return ret

def nthPrime(n):
    """ Generates the nth prime, where n is a zero-based integer """

    # Preconditions: n must be an integer greater than -1
    if not isinstance(n,int) or n < 0:
        raise ValueError("n must be an integer greater than -1")

    # Base case: the 0th prime is 2, 0th function vacuous
    if n == 0:
        return 2,lambda x: 0

    # Get the preceding evaluation
    p_nMinusOne,fn_nMinusOne = nthPrime(n-1)

    # Define the function for the Nth prime
    fn_n = lambda x: fn_nMinusOne(x) + cosProduct(x,p_nMinusOne)

    # Evaluate it (I need a solver here if it's tractable!)
    for k in xrange(p_nMinusOne+1,int(p_nMinusOne**2.718281828)):
        if fn_n(k) == 0:
            p_n = k
            break

    # Return the Nth prime and its function
    return p_n,fn_n

Um exemplo rápido:

>>> [nthPrime(i)[0] for i in range(20)]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

O problema é que agora estou passando dos limites, matematicamente e como cientista da computação. Especificamente, não sou competente com a análise de Fourier , com a definição de coberturas uniformes ou com o plano complexo em geral, e estou preocupado que essa abordagem seja totalmente errada ou oculte um horror à espreita de um problema 3SAT que a eleva a NP-completude.

Portanto, tenho três perguntas aqui:

  1. Dada minha recorrência concisa acima, é possível calcular deterministicamente ou estimar a localização dos zeros no tempo e espaço polinomial?
  2. Em caso afirmativo ou não, está ocultando outros subproblemas que tornariam intratável uma solução polytime ou polyspace?
  3. E se, por algum milagre (1) e (2) persistir, que melhorias dinâmicas na programação você faria para satisfazer essa recorrência, de alto nível? Claramente, a iteração sobre os mesmos números inteiros por meio de múltiplas funções é deselegante e bastante dispendiosa.
MrGomez
fonte
E para aqueles que ainda estão aqui, apesar da minha parede de texto: não tenho certeza se isso se reduz ao Riemann zeta, dando-lhe a mesma complexidade. Mas não acredito que sim.
MrGomez
1
1) Quais tags você gostaria? Você pode criá-los você mesmo usando-os. 2) Por favor, forneça uma definição geral para , ou seja, o que é ? 3) Se você não obtiver uma resposta sobre isso depois de uma semana mais ou menos, convém movê-lo para a cstheory.SE. f ( p n )ff(pn)
Raphael
1
Não estou acompanhando tudo no seu post. Eu acho que você quer dizer NP-complete não NP. Geralmente, provar que uma função teórica dos números é NP-completa é uma tarefa bastante difícil, pois muitas vezes faltam / ocultam qualquer estrutura combinatória que nos permita projetar dispositivos para a redução.
Kaveh
1
Revisão concluída. Certamente haverá outras questões ocultas, mas minha representação original foi completamente errada. Eu deveria consultar o meu eu 24 horas mais novo e dar a ele uma atualização sobre as definições adequadas de . De qualquer forma, agradeço sua paciência e suas edições até agora. As tags atuais também estão agora para minha satisfação. :)f(x)
MrGomez
Em relação a , não é suficiente "verificar" todos os números primos menores em oposição a todos os números menores? f
Raphael

Respostas:

1

O artigo a seguir mostra que o PRIMES está em P (também ganhou o prêmio Gödel em 2006):

http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf

Ao definir a solução do procedimento de minimização da N-prime para o algoritmo AKS PRIMES (módulo a subtração), podemos obter efetivamente uma solução tratável para a relação de recorrência (se você puder provar que o gap principal é fornecido pela relação de recorrência).

Os códigos-fonte podem ser encontrados na internet. Não estou apontando para eles aqui porque não os verifiquei pessoalmente.

No entanto, como ainda podemos ter o limite superior de para verificar todos os números ...n

user13675
fonte
1
A página Rosettacode é completamente incorreta. Este não é o teste de primalidade da AKS e é uma reafirmação da divisão de teste por todos os números inteiros menores que n. Por outro lado, notar que a primalidade está em P e ver se isso lança alguma luz sobre a questão original vale a pena perguntar.
DanaJ
Bom ponto ... Vou corrigir isso ...
user13675
1
Primes em P não implica que possamos gerar números primos deterministicamente em tempo polinomial. É um problema aberto em aberto. ( é uma função exponencial do tamanho da entrada, que é .) lgnnlgn
Kaveh