# Interpretation of co-NPCompleteness?

Given a Problem $$A$$ that has an answer $$true$$ if and only if both conditions $$1$$ and $$2$$ are $$false$$, for some conditions 1 and 2.

Whether condition $$2$$ is $$true$$ can be tested with certainty in deterministic polynomial time. Thus, we can say that answer to an instance of $$A$$ is $$false$$ in polynomial time (in case condition $$2$$ holds). If condition $$2$$ is $$false$$, we still need to test condition $$1$$.

Checking if condition $$1$$ is $$true$$ is an NP-complete problem.

Can we thus conclude that the original problem $$A$$ with both conditions is coNP-complete?

As far as I understand your problem statement is as following:

Given a Problem $A$ that has an answer $true$ if and only if both (some) conditions 1 or 2 are $false$.

We have a decision problem $A(w) = \overline{B(w)} \wedge \overline{C(w)}$, where $B$ and $C$ correspond to the conditions 1 and 2 respectively.

Whether condition 2 is $true$ can be tested with certainty in polynomial time.

$C \in P$.

Checking if condition 1 is $true$ on $A$ is an NPComplete problem (if we consider all possible instances of $A$).

$B \in NP$ and $B$ is $NP$-hard.

(Please, correct me if I misunderstood the problem statement)

So, let's rewrite the statement using the language notation: $L_B \in NP$, $L_C \in P$, and $L_A = \overline{L}_B \cap \overline{L}_C$.

By definition $L_A \in coNP$ if $\overline{L}_A \in NP$. But $\overline{L}_A = L_B \cup L_C$ (De Morgan law). Since we are given that $L_B \in NP$ and $L_C \in P$, $L_B \cup L_C$ is in $NP$ as well. So, $L_A$ is in $coNP$.

Now, take $\overline{L_C} = \emptyset$ which is clearly is in $P$, and so is $L_C = \Sigma^*$. For any $NP$-complete language $L_B$, $L_B \cup L_C = \Sigma^*$. But $\Sigma^*$ is not $coNP$-complete.

• Thank you. The interpretation is correct, but the condition of $B \in NP$ is stronger (as testing truth of $B$ on problem instance of $A$ is NPComplete, not just NP). Would that imply, $L_A$ is $coNPComplete$ and not just $coNP$? Jun 24, 2017 at 19:41
• Not always. Updated my answer. Jun 24, 2017 at 19:56
• I understand. Since we have two conditions, if either one of them is proper subset of another then the subset condition/language becomes redundant. So, if we assume neither of 2 is proper subset of another, can we claim the problem is co-NPComplete? Jun 24, 2017 at 20:13
• Let $L_B$ be a $NP$-complete problem. Take a string $w$ not in $L_B$ and define $L_C=\{w\}$. Clearly $L_C \in P$, and union of $L_B \cup \{w\}$ is still $NP$-complete. If it was also $coNP$-complete, then we would have $NP = coNP$ which is unlikely (open question in fact). Jun 24, 2017 at 21:28
• Agreed. but in original problem above, testing if condition $1$ is $true$ for $B$ is NPC (as stated). But, in the original problem, is dealing with the negation of $1$, so the language is complement of $1$ i.e. of an NPC language. So, wouldn't a complement of an NPC language be a coNPC ? Jun 25, 2017 at 5:17

Let $$C_1$$ and $$C_2$$ be languages representing the conditions $$1$$ and $$2$$, respectively. Then, $$C_1 \in \text{NP-complete}$$ and $$C_2 \in \text{PTIME}$$, and by writing down formally what you mentioned, we get $$A = \overline{C_1} \cap \overline{C_2}$$.

Now you can use the following claim:

Claim: A language $$L$$ is NP-complete iff $$\overline{L}$$ is coNP-complete.

So to understand whether $$A$$ is coNP-complete or not, you can check whether its complement is NP-complete. In your case, $$\overline{A} = C_1 \cup C_2$$, and since $$C_2$$ can be any problem in $$PTIME$$, then $$\overline{A}$$ can be a "very simple language". I leave the details to you.

Note: the important thing here is the above claim. To understand coNP-completeness, it is sufficient to understand NP-completeness.