# What is the name of the complexity class for the optimization version of co-NP-complete and coNexpTime-complete problems?

I know that the optimization version of NP-complete problems belong in NPO. What about co-NP-complete problems? Is there a co-NPO class, or is it just NPO?

I've also never seen the name for the complexity class of optimization problems whose decision version is NExpTime-complete. Is it called NExpTimeO? Is there a co-NExpTimeO complexity class?

There is no difference between $$\mathsf{NPO}$$ and what you would call $$\text{co}\mathsf{NPO}$$.

To explain why, I will try to use a problem as an example:

• the problem $$\texttt{Clique}$$ is defined as follow:

Input: an undirected graph $$G$$ and an integer $$k$$.

Question: does $$G$$ have a $$k$$-clique as a subgraph?

It is well known that this problem is $$\mathsf{NP}$$-complete.

• the problem $$\text{co}\texttt{Clique}$$ is the corresponding $$\text{co}\mathsf{NP}$$-complete problem and is defined as follow:

Input: an undirected graph $$G$$ and an integer $$k$$.

Question: does $$G$$ NOT have a $$k$$-clique as a subgraph?

• the problem $$\texttt{MaxClique}$$ is the corresponding optimisation problem:

Input: an undirected graph $$G = (V, E)$$.

Solution: a subset $$V'\subseteq V$$ such that $$G[V']$$ is a clique.

Optimization: maximize $$|V'|$$.

Now if you are able to solve the optimisation version $$\texttt{MaxClique}$$, you can find the maximal size of a clique in $$G$$. Given this answer, you can find the answer to both the $$\texttt{Clique}$$ and the $$\text{co}\texttt{Clique}$$ question on the same graph, for any $$k$$. See here for a formal definition of $$\mathsf{NPO}$$; you can see that it coincides with a definition we would give for $$\text{co}\mathsf{NPO}$$.

As for your other question, I think that $$\mathsf{NEXPTIME}$$ is often only called $$\mathsf{NEXP}$$, and the optimisation version would be $$\mathsf{NEXPO}$$ (and for the same reason as above, there is no $$\text{co}\mathsf{NEXPO}$$ to consider). But this doesn't seem really studied, for example the complexity zoo doesn't mention it.