Algorithme de temps et de polyspace pour déterminer l'intersection principale de n fonctions monotones discrètes

Quelques informations: je suis informaticien spécialisé dans les loisirs et ingénieur logiciel. Donc, pardonnez si cette invite semble quelque peu hors du champ gauche - je joue régulièrement avec des simulcres mathématiques et des problèmes ouverts quand je n'ai rien de mieux à faire.

En jouant avec l' hypothèse de Riemann , j'ai déterminé que l' écart premier peut être réduit à une relation de récurrence basée sur l'intersection de toutes les fonctions complémentaires formées par les multiples de chaque nombre premier précédent (les observateurs avisés noteront qu'il s'agit d'une généralisation de le tamis d'Ératosthène ). Si cela n'a aucun sens pour vous, ne vous inquiétez pas - c'est toujours une question de premier plan.$n-1$

En voyant comment ces fonctions étaient liées, je me suis rendu compte que l'instance suivante de chaque nombre premier peut être réduite à la première intersection de ces fonctions, se répétant à l'infini. Cependant, je n'ai pas pu déterminer si cela est traitable en polytime et en polyspace. Ainsi: ce que je recherche, c'est un algorithme qui puisse déterminer la première intersection de discrètes (et, le cas échéant, monotones) dans le temps et l'espace polynomial. Si aucun algorithme de ce type n'existe actuellement ou ne peut exister, une preuve laconique ou une référence le mentionnant est suffisante.$n$

Le plus proche que je puisse trouver jusqu'à présent est l'algorithme de projection de Dykstra (oui, c'est RL Dykstra, pas Edsger Dijkstra ), qui je crois se réduit à un problème de programmation entière et est donc NP-difficile. De même, si l'on effectue une intersection d'ensemble transitif de tous les points applicables (tels qu'ils sont actuellement compris comme étant bornés), nous devons toujours nous contraindre à un espace exponentiel pour notre récurrence en raison de la limite faible actuelle de nombres premiers pour tout réel (et donc, espace pour chaque nombre premier ).$\ln(m)$$m$$e^n$$n$

Globalement, je me demande si ma compréhension de la réduction du problème est fausse. Je ne m'attends pas à résoudre l'hypothèse de Riemann (ou tout problème profond et ouvert dans cet espace) de si tôt. Je cherche plutôt à en savoir plus à ce sujet en jouant avec le problème, et j'ai rencontré un problème dans mes recherches.

Déterminer si deux fonctions monotones données comme des programmes se croisent n'est pas calculable. De même, la détermination de la première intersection sous la promesse qu'elle existe est «arbitrairement difficile» (certainement pas le polytime).

$P$$f_P$$n$$1$$P$$n$$f_P$$1$$P$$P$$f_P$$1$

$T$$T$