3
$\begingroup$

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?

$\endgroup$

2 Answers 2

4
$\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$
7
  • $\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, 2017 at 19:41
  • $\begingroup$ Not always. Updated my answer. $\endgroup$
    – fade2black
    Jun 24, 2017 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, 2017 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, 2017 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, 2017 at 5:17
1
$\begingroup$

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.

$\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.