Algoritmo Polytime e polyspace para determinar a interseção principal de n funções monotônicas discretas

16

Algum frontmatter: eu sou um cientista de computador recreacional e empregado um engenheiro de software. Então, desculpe se esse prompt parecer um pouco fora do campo esquerdo - eu brinco rotineiramente com simulações matemáticas e abro problemas quando não tenho nada melhor para fazer.

Enquanto brincava com a hipótese de Riemann , determinei que o intervalo principal pode ser reduzido a uma relação de recorrência com base na interseção de todas as funções complementares formadas pelos múltiplos de cada número primo anterior (observadores interessados ​​observam que esta é uma generalização de a peneira de Eratóstenes ). Se isso não faz absolutamente sentido para você, não se preocupe - ainda é o principal.n1

Vendo como essas funções se relacionavam, percebi que a próxima instância de cada primo pode ser reduzida à primeira interseção dessas funções, recorrendo infinitamente à frente. No entanto, não pude determinar se isso é tratável em polytime e polyspace. Assim, o que estou procurando é um algoritmo que possa determinar a primeira interseção de funções discretas (e, se aplicável, monotônicas) no tempo e no espaço polinomiais. Se atualmente não existe ou pode existir esse algoritmo, uma prova concisa ou uma referência afirmando isso é suficiente.n

O mais próximo que posso encontrar até agora é o algoritmo de projeção de Dykstra (sim, é RL Dykstra, não Edsger Dijkstra ), que eu acredito que se reduz a um problema de programação inteira e, portanto, é difícil para NP. Da mesma forma, se alguém realiza uma interseção transitiva de todos os pontos aplicáveis ​​(como atualmente são delimitados), ainda devemos nos restringir ao espaço exponencial para nossa recorrência devido ao atual limite fraco de primos para qualquer m real (e, portanto, e n espaço para cada primo n ).ln(m)menn

Globalmente, estou me perguntando se meu entendimento da redução do problema está errado. Não espero resolver a hipótese de Riemann (ou qualquer problema profundo e aberto neste espaço) em breve. Em vez disso, estou procurando aprender mais sobre isso, brincando com o problema, e encontrei um problema na minha pesquisa.

MrGomez
fonte
1
Por interseção de duas funções e g , digamos, você quer dizer valores n como f ( n ) = g ( n ) ? fgnf(n)=g(n)
18712 Dave Clarke #
@DaveClarke Correct. Perdoe minha discrepância e subespecificação do problema; Admito abertamente que esta questão pode ser melhorada agora que o enquadramento da pergunta é um pouco mais claro em minha mente.
MrGomez 14/05
@ MrGomez, essas são funções monotônicas arbitrárias ou há outra restrição que você possa colocar sobre elas?
user834
@ user834 Recauchutando minha intenção original com esta postagem, isso foi para explorar a interseção principal de um conjunto de funções vinculadas por uma variável (por exemplo: ). Desde então, resumi a equação em termos de funções trigonométricas contínuas, em vez de monótonos, para ver se um solucionador de polimetal e espaço pode existir para a composição. Até agora, sem sorte, mas não tive a chance de ver isso nas últimas semanas. mEun(n>22n+13n+13n+2)
MrGomez
Dykstra e Dijkstra são o mesmo nome. "y" é uma ligadura para "ij", que é uma "letra" no alfabeto holandês: en.wikipedia.org/wiki/IJ_(digraph) .
Yuval Filmus 23/03

Respostas:

5

Determinar se duas funções monótonas dadas como programas se cruzam não é computável. Da mesma forma, a determinação da primeira interseção sob a promessa de que ela existe é "arbitrariamente difícil" (definitivamente não é hora politica).

PfPn1PnfP1PPfP1

TT

Yuval Filmus
fonte
Eu realmente gosto desta resposta. É conciso, geral o suficiente para abranger o escopo da minha pergunta e relaciona meu problema a um aspecto que não considerei: a intratabilidade do problema de parada. Isso fará bem. Obrigado!
MrGomez