# Interpretation of co-NPCompleteness?

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

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

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

Can we thus conclude that the original problem with both conditions is co-NPComplete?

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$? – J.Doe Jun 24 '17 at 19:41
• Not always. Updated my answer. – fade2black Jun 24 '17 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? – J.Doe Jun 24 '17 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). – fade2black Jun 24 '17 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 ? – J.Doe Jun 25 '17 at 5:17