-1
$\begingroup$

Dear StackExchange community,

I have a question, or better phrased I am confused and would like to be enlightened by you! So assume we have a (optimization) problem like that:

Instance: Let $f:\mathbb{R} \rightarrow \mathbb{R}$, and let $k \in \mathbb{N}$. Question: Does there exist a $x \in \mathbb{R}$, s.t. $f(x) < k$?

Is this problem computable? I am not $100\%$ sure, whether it is or not, but I think it is not (and therefore obviously also not in NP). Note that I do not put any assumptions on $f$.

Here (click on the spoiler) you find my argument, why I think it is not computable (and also not semi-decidable):

For the sake of the argument assume that there only exists (exactly) one (unknown) value $c$ s.t. $f(c) < k$. Further, contrary to common assumptions, we assume that we can express real numbers in our computer and that we can somehow express (or at least evaluate) $f$. With the assumptions stated, here is my (honestly very high level) line of reasoning: Any algorithm which implements our decision problem necessarily has to somehow try out all possible input values of $f$ (as we do not have any information about $f$). As $R$ is uncountable infinite (aka. not enumerable), there is no hope to enumerate all values $x \in \mathbb{R}$, and therefore, any algorithm might, or might not halt (it is not even guaranteed to halt in the positive case, so not even semi-decidable!). Reasoning and implications beyond my question: I think if the above holds, if we switch $f$ for $g:\mathbb{Q} \rightarrow \mathbb{Q}$ (or any countable domain of the function, in general), the decision-problem should be semi-decidable, but not computable (and therefore, as a result, optimization in Machine Learning should be not computable).

Note that I did not find the exact same question, as most other questions regarding optimization and complexity refer to the finite case (I did not find any regarding the infinite case...). Though, I provide you with some research I did in this matter, which did not answer my questions: Thesis about optimization and complexity, Some paper, Computational Complexity of Christos H. Padadimitriou, and Discussion on a StackExchange.

I am looking forward to your thoughts and a discussion about this.

Best, Thinklex.

$\endgroup$
2
  • $\begingroup$ How is $f$ represented? That is crucial to specify. $\endgroup$
    – D.W.
    Mar 16 at 5:33
  • $\begingroup$ Thank you for your clarification request! I thought about it in a way that $f$ actually is a function in nature (or an Oracle function), which we can ask to give us a value, provided an input, but we have no clue about its actual representation (and we assume no Analog-Digital-Conversion loss, whatsoever...). But please let me know, what you think might happen depending on how we specify, as I do not know, what the implications might be. $\endgroup$
    – Thinklex
    Mar 17 at 23:00

1 Answer 1

0
$\begingroup$

Your reasoning seems correct to me, though you should take care making statements such as "Any algorithm which implements our decision problem necessarily has to somehow try out all possible input values of $f$."

However, this really isn't surprising. You could encode a non-decidable language into a function that outputs 1 if the input is in the language and 0 if not. Such a function could have its domain even be as small as $\mathbb{N}$. All optimization problems are about a restricted class of functions. So I am not sure your conclusion "optimization in Machine Learning should be not computable" is justified.

$\endgroup$
1
  • $\begingroup$ Thank you very much for your answer! Yes you are right, this statement is bold and should be handled with care. Do you know a better argument? Further, thank you for your input about the general stmt. about the non-decidable language. So I assume, this is the case, as we (might) have in Machine Learning some further assumptions on the function $f$? $\endgroup$
    – Thinklex
    Mar 17 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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