<p>First, for context, I want to mention that the classes described in that answer are not standard. Like a decision problem, an optimization problem is NP-hard if solving it (computing an optimal solution) in polynomial time allows you to solve any problem in NP in polynomial time.</p>
<p>But, we can still consider the question you asked. You are right that a NDTM can't compare solutions computed on different branches. However, we don't need to. Instead, we can think about how we normally convert optimization problems to NP problems, and vice versa. First we compute upper and lower bounds for the optimal value, call them <span class="math-container">$L$</span> and <span class="math-container">$U$</span>. For convenience, let us assume we are dealing with a minimization problem, and the cost of a solution is always an integer. We can perform a binary search on <span class="math-container">$[L,U] \cap \mathbb{Z}$</span> by solving <span class="math-container">$O\big(\log(U-L)\big)$</span> instances of the decision problem &quot;Given, <span class="math-container">$x \in X$</span>, and <span class="math-container">$f(x,\cdot): L(x) \to \mathbb{Z}$</span>, and integer <span class="math-container">$k$</span> does there exists <span class="math-container">$y \in L(x)$</span> such that <span class="math-container">$f(x,y) \leq k$</span>?&quot; This can be solved in polynomial time with our NDTM.</p>
<p>Edit:</p>
<p>As @EmilJerabek pointed out, what I have described above is not actually an NTM but a DTM with an NP oracle. I was focused on the spirit of the question, which I interpreted as &quot;Given the power of an NTM, are there problems in <span class="math-container">$NPO$</span> that still cannot be solved in polynomial time?&quot; However, the answer to the the technical question you asked, &quot;Are there problems in <span class="math-container">$NPO$</span> that even an NTM can't solve in polynomial time?&quot; is &quot;yes&quot; (under standard assumptions). I would contend that the fact we need an DTM with an NTM oracle is a relic of the fact that the formal definition of NTM was created with decision problems in mind. The power of an NTM is that it &quot;accepts&quot; if any of its computation branches ends in an accepting state, which doesn't mean anything outside of the context of decision problems.</p>
<p>However, a larger problem is that what I described above doesn't actually solve the problem. It doesn't actually compute the optimal solution, just the optimal value. It turns out the there are problems where actually computing a solution <span class="math-container">$y$</span> with some property is harder than determining if such a <span class="math-container">$y$</span> exists [see https://en.wikipedia.org/wiki/FNP_(complexity) and https://cseweb.ucsd.edu/~mihir/papers/compip.pdf].
This might be closer to the issue you foresaw when thinking about the exponentially many comparisons an NTM would have to make.</p>

CC BY-SA 4.0
2024-06-18T23:10:07.300Z
There is an inherent asymmetry in the definition of NP between YES instances and NO instances. It is not useful to think of NDTMs as "algorithms". When the answer to an instance is NO the NDTM won't necessarily be efficient in certifying it. In your binary search above, you are assuming that the NDTM will efficiently tell you YES or NO for each query.
Chandra Chekuri
CC BY-SA 4.0
2024-06-18T23:29:56.370Z
That is a good point! The properties of the NPO class defined in the linked answer state "$f$ can be evaluated in polynomial time" and "... there is a deterministic algorithm that decides in polynomial time whether $y \in L(x)$." Thus given an arbitrary string $y$, one can determine if $y \in L(x)$ and if so, evaluate $f(x,y)$ in polynomial time, so the NDTM does answer each query efficiently. However, if you tweaked the definition, that asymmetry could change the answer.
NaturalLogZ
CC BY-SA 4.0
2024-06-19T04:58:31.117Z
But an NTM does not "answer queries". What you described is not an NTM, but a DTM with an NP-oracle, and it only shows that the answer can be computed in $\mathrm{FP^{NP}}$.
Emil Jeřábek
CC BY-SA 4.0
2024-06-19T17:37:20.780Z
Thank you for answerng, it made things clearer! At first I was confused because there is no explicit bound on $U - L$ in the definition which lead me to think that the number of instances we would need to solve in our binary search could technically still be exponential. However in such a pathological instance, where e. g. $U - L = \mathcal{O}(2^{(2^{\vert x \vert})})$, $f$ would not be computable in polynomial time anymore since we would need $\mathcal{O}(2^{\vert x \vert})$ bits to even encode the result. With this, I think I finally understand. (But feel free to correct me)
SmartRock
CC BY-SA 4.0
2024-06-18T22:46:59.817Z
2024-06-20T16:58:07.693Z
2024-06-20T16:58:07.693Z
NaturalLogZ
<p>Consider an <span class="math-container">$\mathit{NPO}$</span> problem <span class="math-container">$O = (X,L,f,\mathit{opt})$</span> according to the definition of <span class="math-container">$\mathit{NPO}$</span> found in <a href="https://cs.stackexchange.com/a/476">this</a> answer.
What I don't fully understand is what happens if we use a NDTM (non-deterministic Turing machine) to solve it while there are exponentially many (<span class="math-container">$\Theta(2^{\vert x \vert})$</span>) feasible solutions in <span class="math-container">$L(x)$</span> for the instances <span class="math-container">$x \in X$</span>.</p>
<p>I understand how the NDTM could non-deterministically generate all feasible solutions in <span class="math-container">$L(x)$</span> for a given instance <span class="math-container">$x$</span> and compute <span class="math-container">$f$</span> for each one: The computation could non-deterministically branch out with each branch computing one distinct member of <span class="math-container">$L(x)$</span>, and then its cost/value by computing <span class="math-container">$f$</span>.</p>
<p>But how would it then determine which solution has the optimal cost/value?<br />
In my understanding that would require <span class="math-container">$\Theta(2^{\vert x \vert})$</span> comparisons and I don't see how, even non-deterministically, we could do them in polynomial time.<br />
My reasoning is that every feasible solution, and its cost/value, &quot;lives&quot; on its own computation branch. To compare all of them however, we would need them on the same branch.</p>
<p>Does this mean that there are (conterintuitively) problems in <span class="math-container">$\mathit{NPO}$</span> that even a NDTM can't solve in polynomial time, or am I getting something wrong?</p>

CC BY-SA 4.0
2024-06-19T12:21:33.470Z
You have to use binary search.
Giorgio Camerani
<complexity-classes><optimization><nondeterminism>
Are there NPO (NP Optimization) problems that would require more than polynomial time even on a non-deterministic machine?
SmartRock
# Are there NPO (NP Optimization) problems that would require more than polynomial time even on a non-deterministic machine?

(Asked by: username_0 on 2024-06-18)

Consider an $\mathit{NPO}$ problem $O = (X,L,f,\mathit{opt})$ according to the definition of $\mathit{NPO}$ found in [this](https://cs.stackexchange.com/a/476) answer.
What I don't fully understand is what happens if we use a NDTM (non-deterministic Turing machine) to solve it while there are exponentially many ($\Theta(2^{\vert x \vert})$) feasible solutions in $L(x)$ for the instances $x \in X$.

I understand how the NDTM could non-deterministically generate all feasible solutions in $L(x)$ for a given instance $x$ and compute $f$ for each one: The computation could non-deterministically branch out with each branch computing one distinct member of $L(x)$, and then its cost/value by computing $f$.

But how would it then determine which solution has the optimal cost/value?  
In my understanding that would require $\Theta(2^{\vert x \vert})$ comparisons and I don't see how, even non-deterministically, we could do them in polynomial time.  
My reasoning is that every feasible solution, and its cost/value, "lives" on its own computation branch. To compare all of them however, we would need them on the same branch.

Does this mean that there are (conterintuitively) problems in $\mathit{NPO}$ that even a NDTM can't solve in polynomial time, or am I getting something wrong?

**Tags:** complexity-classes, optimization, nondeterminism
> **Comments:**
> **username_1**: You have to use binary search.  

---

## 1 answers

### Answer by username_2 on 2024-06-18. Score: -1 | Accepted answer

First, for context, I want to mention that the classes described in that answer are not standard. Like a decision problem, an optimization problem is NP-hard if solving it (computing an optimal solution) in polynomial time allows you to solve any problem in NP in polynomial time.

But, we can still consider the question you asked. You are right that a NDTM can't compare solutions computed on different branches. However, we don't need to. Instead, we can think about how we normally convert optimization problems to NP problems, and vice versa. First we compute upper and lower bounds for the optimal value, call them $L$ and $U$. For convenience, let us assume we are dealing with a minimization problem, and the cost of a solution is always an integer. We can perform a binary search on $[L,U] \cap \mathbb{Z}$ by solving $O\big(\log(U-L)\big)$ instances of the decision problem "Given, $x \in X$, and $f(x,\cdot): L(x) \to \mathbb{Z}$, and integer $k$ does there exists $y \in L(x)$ such that $f(x,y) \leq k$?" This can be solved in polynomial time with our NDTM.

Edit:

As @EmilJerabek pointed out, what I have described above is not actually an NTM but a DTM with an NP oracle. I was focused on the spirit of the question, which I interpreted as "Given the power of an NTM, are there problems in $NPO$ that still cannot be solved in polynomial time?" However, the answer to the the technical question you asked, "Are there problems in $NPO$ that even an NTM can't solve in polynomial time?" is "yes" (under standard assumptions). I would contend that the fact we need an DTM with an NTM oracle is a relic of the fact that the formal definition of NTM was created with decision problems in mind. The power of an NTM is that it "accepts" if any of its computation branches ends in an accepting state, which doesn't mean anything outside of the context of decision problems.

However, a larger problem is that what I described above doesn't actually solve the problem. It doesn't actually compute the optimal solution, just the optimal value. It turns out the there are problems where actually computing a solution $y$ with some property is harder than determining if such a $y$ exists [see https://en.wikipedia.org/wiki/FNP\_(complexity) and https://cseweb.ucsd.edu/~mihir/papers/compip.pdf].
This might be closer to the issue you foresaw when thinking about the exponentially many comparisons an NTM would have to make.

> **Comments:**
> **username_3**: There is an inherent asymmetry in the definition of NP between YES instances and NO instances. It is not useful to think of NDTMs as "algorithms". When the answer to an instance is NO the NDTM won't necessarily be efficient in certifying it. In your binary search above, you are assuming that the NDTM will efficiently tell you YES or NO for each query.  
> **username_2**: That is a good point! The properties of the NPO class defined in the linked answer state "$f$ can be evaluated in polynomial time" and "... there is a deterministic algorithm that decides in polynomial time whether $y \in L(x)$." Thus given an arbitrary string $y$, one can determine if $y \in L(x)$ and if so, evaluate $f(x,y)$ in polynomial time, so the NDTM does answer each query efficiently. However, if you tweaked the definition, that asymmetry could change the answer.  
> **username_4**: But an NTM does not "answer queries". What you described is not an NTM, but a DTM with an NP-oracle, and it only shows that the answer can be computed in $\mathrm{FP^{NP}}$.  
> **username_0**: Thank you for answerng, it made things clearer! At first I was confused because there is no explicit bound on $U - L$ in the definition which lead me to think that the number of instances we would need to solve in our binary search could technically still be exponential. However in such a pathological instance, where e. g. $U - L = \mathcal{O}(2^{(2^{\vert x \vert})})$, $f$ would not be computable in polynomial time anymore since we would need $\mathcal{O}(2^{\vert x \vert})$ bits to even encode the result. With this, I think I finally understand. (But feel free to correct me)  

---

