Are there NPO (NP Optimization) problems that would require more than polynomial time even on a non-deterministic machine?

Consider an $$\mathit{NPO}$$ problem $$O = (X,L,f,\mathit{opt})$$ according to the definition of $$\mathit{NPO}$$ found in this 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?

• You have to use binary search. Commented Jun 19 at 12:21

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.

• 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. Commented Jun 18 at 23:10
• 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. Commented Jun 18 at 23:29
• 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}}$. Commented Jun 19 at 4:58
• 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) Commented Jun 19 at 17:37