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$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.