0
$\begingroup$

I don't know this is off-topic (if not, someone can direct me to the proper Stack), but here goes: Let's say there is some algorithm $T$ that can find the integer roots of any arbitrary real-valued continuous univariate function $f(x)$. For any value of $x$, $f$ can be computed efficiently ($O(n^k)$, where $k$ is some small constant). $T$ is similarly efficient. Are there any real life problems that would be benefited by having such an algorithm?

$\endgroup$
2
$\begingroup$

Sure. If this works for any function $f$ that can be computed efficiently, such an algorithm would let you solve any NP problem.

Let $g:\{0,1\}^n \to \{0,1\}$ be an arbitrary function that is efficiently computable. When $x$ is an integer, define $f(x) = g(x_1,\dots,x_n)$ where $x_1\cdots x_n$ is the binary representation of $x$; when $x$ is not an integer, define $f(x)$ to linearly interpolate between $f(\lfloor x \rfloor)$ and $f(\lceil x \rceil)$, i.e.,

$$f(x) = f(\lfloor x \rfloor) + (f(\lceil x \rceil) - f(\lfloor x \rfloor))(x - \lfloor x \rfloor).$$

Then if we apply your algorithm to $f$, we find an efficient way to compute $x_1,\dots,x_n$ such that $g(x_1,\dots,x_n)=0$. This in turn lets you efficiently solve any NP problem.

For instance, you could break the RSA cryptosystem efficiently, you could mint Bitcoin coins efficiently, you could solve optimization and operations research problems efficiently, and so on.


If this is restricted to only $f$ that are low degree polynomials, we already know of algorithms to solve the problem, so it likely would not represent an advance over the state of the art and likely wouldn't have much of an impact in practice, unless your method was significantly more efficient than existing methods.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! This is very interesting, though how can any NP problem be described in such a functions. And about that last comment, like I said $f$ is any function that satisfy the requirements above. $\endgroup$ – Quote Dave Apr 19 at 23:49
  • 1
    $\begingroup$ @QuoteDave, for instance, you can express SAT (satisfiability) in this way -- I'll let you work out the details. $\endgroup$ – D.W. Apr 19 at 23:53
  • $\begingroup$ Ok, this is still great. Checkmark! $\endgroup$ – Quote Dave Apr 19 at 23:59
  • 1
    $\begingroup$ +1, also for a rare correct usage of the phrase "NP problem" :) $\endgroup$ – j_random_hacker Apr 20 at 19:49

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.