# Assert the existence of a point with the following property in P time

For $$f : \mathbb{R}^{n \times 1} \to \mathbb{R}$$ a double differentiable function with bounded hessian, not necessarily convex, is any known polynomial algorithm, in the general case, which can assert if for a given $$C \in \mathbb{R}^{n \times 1}$$ with $$\|C\| \geq k > 0$$ exists $$X \in \mathcal{B}(0_{n \times 1}, R)$$ such that $$f(X) + C^T \cdot X = 0$$

Consider $$k$$ and $$R$$ as some positive constants. Is any work in this direction published?

I doubt you can do so in polynomial time without any additional condition.

Let $$g$$ be an arbitrary polynomial function, and let $$f$$ be defined by $$f(X) = g(X) - C^{T}X$$ over $$B(0, R)$$, and an appropriate extension so that it's twice differentiable with bounded Hessian over $$\mathbb{R}^{n}$$. Then, $$f(X) + C^{T}X = 0$$ reduces to $$g(X) = 0$$, i.e., your setting is equivalent to finding a root of $$g$$ in $$B(0, R)$$.

(I believe that deciding whether an arbitrary polynomial has a root of at most norm $$R$$ is already NP-hard, but I'm not 100% sure).

Now, since 3SAT can be written as finding a root of a polynomial (make a polynomial for each clause and multiply all of them), finding a root of an arbitrary polynomial is NP-hard.

Thus, unless P = NP, there is little chance that you can solve your problem for general $$f$$ in polynomial time. (note that the value of $$R, k$$ are insignificant, since we can always re-scale everything).

• Assuming that an algorithm is found, but which requires for instance something like $\|C\| \geq \| \frac{\partial f}{\partial x} \| } + R$. Can this be still used to assert the zeros of $f(x)$ ? Can you expand a little on the insignificancy of $R$ and $k$ ? May 30 at 16:01
• For the example I give, you can assume without loss of generality that $R=1$ by replacing $X$ with $X / R$. This does not affect the assumptions on $f$. You can also assume w.l.o.g that $k=1$ by multiplying $f$ by $1/k$. May 31 at 20:23