16
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ By intersection of two functions $f$ and $g$, say, do you mean values $n$ such $f(n)=g(n)$? $\endgroup$ – Dave Clarke May 14 '12 at 10:51
  • $\begingroup$ @DaveClarke Correct. Pardon my terseness and underspecification of the problem; I openly admit that this question can be improved now that the question framing is a bit clearer in my mind. $\endgroup$ – MrGomez May 14 '12 at 18:44
  • $\begingroup$ @MrGomez, these are arbitrary monotonic functions or is there another restriction you can place on them? $\endgroup$ – user834 Jun 25 '12 at 4:56
  • $\begingroup$ @user834 Retreading my original intent with this post, this was for exploring the leading intersection of an ensemble of functions bound by one variable (for example: $min(n > 2 \mid 2n+1 \cap 3n+1 \cap 3n+2)$). I've since summarized the equation in terms of continuous trigonometric functions instead of monotones to see if a poly- time and space solver can exist for the composition. So far, no luck, but I haven't had a chance to look at it in recent weeks. $\endgroup$ – MrGomez Jun 26 '12 at 23:27
  • $\begingroup$ Dykstra and Dijkstra are the same name. "y" is a ligature for "ij", which is a "letter" in the Dutch alphabet: en.wikipedia.org/wiki/IJ_(digraph). $\endgroup$ – Yuval Filmus Mar 23 '13 at 14:02
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I really like this answer. It's concise, general enough to encompass the scope of my question, and relates my problem to an aspect I did not consider: the intractability of the halting problem. This will do nicely. Thank you! $\endgroup$ – MrGomez Mar 27 '13 at 8:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.