Some frontmatter: I'm a recreational computer scientist and employed software engineer. So, pardon if this prompt seems somewhat out of left field -- I routinely play with mathematical simulcra and open problems when I have nothing better to do.
While playing with the Riemann hypothesis, I determined that the prime gap can be reduced to a recurrence relation based on the intersection of all $n-1$ complementary functions formed by the multiples of each previous prime number (keen observers will note this is a generalization of the Sieve of Eratosthenes). If this makes absolutely no sense to you, don't worry -- it's still frontmatter.
Seeing how these functions related, I realized that the next instance of each prime can be reduced to the first intersection of these functions, recurring forward infinitely. However, I could not determine if this is tractable in polytime and polyspace. Thus: what I'm looking for is an algorithm that can determine the first intersection of $n$ discrete (and, if applicable, monotonic) functions in polynomial time and space. If no such algorithm currently exists or can exist, a terse proof or reference stating so is sufficient.
The closest I can find so far is Dykstra's projection algorithm (yes, that's R. L. Dykstra, not Edsger Dijkstra), which I believe reduces itself to a problem of integer programming and is, therefore, NP-hard. Similarly, if one performs a transitive set intersection of all of the applicable points (as they're currently understood to be bounded), we must still constrain ourselves to exponential space for our recurrence due to the current weak bound of $\ln(m)$ primes for any real $m$ (and therefore, $e^n$ space for each prime $n$).
Globally, I'm wondering if my understanding of the reduction of the problem is wrong. I don't expect to solve the Riemann hypothesis (or any deep, open problem in this space) any time soon. Rather, I'm seeking to learn more about it by playing with the problem, and I've hit a snag in my research.
Asked By : MrGomez
Answered By : Yuval Filmus
Determining whether two monotone functions given as programs intersect is non-computable. Similarly, determining the first intersection under the promise that it exists is "arbitrarily hard" (definitely not polytime).
Given a program $P$, define a function $f_P$ which, for input $n$, is $1$ if $P$ stops after $n$ steps or less. The first intersection of $f_P$ and the constant function $1$ is the running time of $P$, if $P$ halts. So no program can decide whether $f_P$ and $1$ intersect.
Similarly, the time hierarchy theorem shows that for no recursive time bound $T$, the first intersection point can be found in time $T$, even under the promise that it exists. Using the space hierarchy theorem, you can get the same for space.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1828
0 comments:
Post a Comment
Let us know your responses and feedback