patternMinor
Interpretation of co-NPCompleteness?
Viewed 0 times
interpretationnpcompletenessstackoverflow
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#77181, answer score: 4
Revisions (0)
No revisions yet.