3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.