1
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

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.