<p>Your reasoning seems correct to me, though you should take care making statements such as &quot;Any algorithm which implements our decision problem necessarily has to somehow try out all possible input values of <span class="math-container">$f$</span>.&quot;</p>
<p>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 <span class="math-container">$\mathbb{N}$</span>. All optimization problems are about a restricted class of functions. So I am not sure your conclusion &quot;optimization in Machine Learning should be not computable&quot; is justified.</p>

CC BY-SA 4.0
2024-03-17T22:51:33.113Z
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$?
Thinklex
CC BY-SA 4.0
2024-03-15T18:08:23.820Z
2024-03-15T18:08:23.820Z
NaturalLogZ
<p>Dear StackExchange community,</p>
<p>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:</p>
<blockquote>
<p>Instance: Let <span class="math-container">$f:\mathbb{R} \rightarrow \mathbb{R}$</span>, and let <span class="math-container">$k \in \mathbb{N}$</span>. Question: Does there exist a <span class="math-container">$x \in \mathbb{R}$</span>, s.t. <span class="math-container">$f(x) &lt; k$</span>?</p>
</blockquote>
<p>Is this problem computable? I am not <span class="math-container">$100\%$</span> sure, whether it is or not, but I think it is not (and therefore obviously also not in <em>NP</em>).
Note that I do not put any assumptions on <span class="math-container">$f$</span>.</p>
<p>Here (click on the spoiler) you find my argument, why I think it is <strong>not</strong> computable (and also not semi-decidable):</p>
<blockquote class="spoiler">
<p> For the sake of the argument assume that there only exists (exactly) one (unknown) value <span class="math-container">$c$</span> s.t. <span class="math-container">$f(c) &lt; k$</span>. 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) <span class="math-container">$f$</span>. <strong>With the assumptions stated, here is my (honestly very high level) line of reasoning:</strong> Any algorithm which implements our decision problem necessarily has to somehow try out all possible input values of <span class="math-container">$f$</span> (as we do not have any information about <span class="math-container">$f$</span>). As <span class="math-container">$R$</span> is uncountable infinite (aka. not enumerable), there is <strong>no hope to enumerate all values</strong> <span class="math-container">$x \in \mathbb{R}$</span>, 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!). <strong>Reasoning and implications beyond my question:</strong> I think if the above holds, if we switch <span class="math-container">$f$</span> for <span class="math-container">$g:\mathbb{Q} \rightarrow \mathbb{Q}$</span> (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).</p>
</blockquote>
<p>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: <a href="https://www.research-collection.ethz.ch/bitstream/handle/20.500.11850/83190/eth-8574-02.pdf" rel="nofollow noreferrer">Thesis about optimization and complexity</a>, <a href="https://dl.acm.org/doi/pdf/10.1145/12130.12138" rel="nofollow noreferrer">Some paper</a>, Computational Complexity of Christos H. Padadimitriou, and <a href="https://mathoverflow.net/questions/442071/is-non-convex-optimisation-really-in-np-class">Discussion on a StackExchange</a>.</p>
<p>I am looking forward to your thoughts and a discussion about this.</p>
<p>Best, Thinklex.</p>

CC BY-SA 4.0
2024-03-16T05:33:54.803Z
How is $f$ represented?  That is crucial to specify.
D.W.
CC BY-SA 4.0
2024-03-17T23:00:20.043Z
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.
Thinklex
<cc.complexity-theory><optimization><computability>
Computability/Complexity of optimization problems in general
Thinklex
# Computability/Complexity of optimization problems in general

(Asked by: username_0 on 2024-03-15)

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](https://www.research-collection.ethz.ch/bitstream/handle/20.500.11850/83190/eth-8574-02.pdf), [Some paper](https://dl.acm.org/doi/pdf/10.1145/12130.12138), Computational Complexity of Christos H. Padadimitriou, and [Discussion on a StackExchange](https://mathoverflow.net/questions/442071/is-non-convex-optimisation-really-in-np-class).

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

Best, username_0.

**Tags:** cc.complexity-theory, optimization, computability

> **Comments:**
> **username_1**: How is $f$ represented?  That is crucial to specify.  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_2 on 2024-03-15. Score: 0 | Accepted answer

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.

> **Comments:**
> **username_0**: 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$?  

---

