Algoritmo de Polytime y Polyspace para determinar la intersección principal de n funciones discretas monotónicas

Algunos comentarios: soy un informático recreativo e ingeniero de software empleado. Entonces, perdón si este mensaje parece algo fuera del campo izquierdo: juego rutinariamente con simulcra matemática y problemas abiertos cuando no tengo nada mejor que hacer.

Mientras jugaba con la hipótesis de Riemann , determiné que la brecha principal se puede reducir a una relación de recurrencia basada en la intersección de todas las funciones complementarias $n-1$ formadas por los múltiplos de cada número primo anterior (los observadores entusiastas notarán que esto es una generalización de El tamiz de Eratóstenes ). Si esto no tiene absolutamente ningún sentido para ti, no te preocupes, sigue siendo una fuente de atención.

Al ver cómo se relacionaban estas funciones, me di cuenta de que la siguiente instancia de cada primo se puede reducir a la primera intersección de estas funciones, recurriendo hacia adelante infinitamente. Sin embargo, no pude determinar si esto es manejable en polytime y polyspace. Por lo tanto: lo que estoy buscando es un algoritmo que pueda determinar la primera intersección de funciones discretas (y, si corresponde, monótonas) en el tiempo y el espacio polinomiales. Si actualmente no existe o puede existir dicho algoritmo, una prueba concisa o una referencia que lo indique es suficiente. $n$

Lo más cercano que puedo encontrar hasta ahora es el algoritmo de proyección de Dykstra (sí, ese es RL Dykstra, no Edsger Dijkstra ), que creo que se reduce a un problema de programación de enteros y, por lo tanto, es NP-hard. De manera similar, si uno realiza una intersección transitiva de todos los puntos aplicables (como se los considera actualmente limitados), aún debemos limitarnos al espacio exponencial para nuestra recurrencia debido al límite débil actual de los primos para cualquier real (y por lo tanto, espacio para cada primo ). $\ln(m)$ $m$ $e^n$ $n$

A nivel mundial, me pregunto si mi comprensión de la reducción del problema es incorrecta. No espero resolver la hipótesis de Riemann (o cualquier problema profundo y abierto en este espacio) en el corto plazo. Más bien, estoy tratando de aprender más al respecto jugando con el problema, y he encontrado un obstáculo en mi investigación.

algorithms reference-request discrete-mathematics MrGomez
fuente

Por intersección de dos funciones

, por ejemplo, ¿quieres decir valores

tales

f

$f$

g

$g$

n

$n$

f (n) = g (n)

$f(n)=g(n)$

Dave Clarke

@DaveClarke Correcto. Perdone mi brevedad y subespecificación del problema; Admito abiertamente que esta pregunta se puede mejorar ahora que el marco de la pregunta está un poco más claro en mi mente.

MrGomez

@MrGomez, estas son funciones monótonas arbitrarias o ¿hay alguna otra restricción que pueda imponerles?

user834

@ user834 Retransmitiendo mi intención original con esta publicación, esto fue para explorar la intersección principal de un conjunto de funciones unidas por una variable (por ejemplo:

). Desde entonces, he resumido la ecuación en términos de funciones trigonométricas continuas en lugar de monótonos para ver si puede existir un solucionador de tiempo y espacio para la composición. Hasta ahora, no tuve suerte, pero no he tenido la oportunidad de verlo en las últimas semanas.

m i n (n > 2 ∣ 2 n + 1 \cap 3 n + 1 \cap 3 n + 2)

$min(n > 2 \mid 2n+1 \cap 3n+1 \cap 3n+2)$

MrGomez

Dykstra y Dijkstra son el mismo nombre. "y" es una ligadura para "ij", que es una "letra" en el alfabeto holandés: en.wikipedia.org/wiki/IJ_(digraph) .

Yuval Filmus

Determinar si dos funciones monótonas dadas como programas se cruzan no es computable. Del mismo modo, determinar la primera intersección bajo la promesa de que existe es "arbitrariamente difícil" (definitivamente no es polytime).

Dado un programa , defina una función que, para la entrada , sea si detiene después de pasos o menos. La primera intersección de y la función constante es el tiempo de ejecución de , si detiene. Por lo tanto, ningún programa puede decidir si y cruzan. $P$ $f_P$ $n$ $1$ $P$ $n$ $f_P$ $1$ $P$ $P$ $f_P$ $1$

$T$ $T$

Yuval Filmus
fuente

Realmente me gusta esta respuesta. Es conciso, lo suficientemente general como para abarcar el alcance de mi pregunta, y relaciona mi problema con un aspecto que no consideré: la intratabilidad del problema de detención. Esto lo hará bien. ¡Gracias!

MrGomez

Algoritmo de Polytime y Polyspace para determinar la intersección principal de n funciones discretas monotónicas

Respuestas: