1
$\begingroup$

I've had the following question on a test and I answered: 'False', my answer was incorrect and I'm trying to understand why.

$VC = \{<G,k> |\ G =$ undirected graph with a vertex cover of size $k\}$

$IS = \{<G,k>|\ G =$ undirected graph with an independent set of size $k\}$

Ture or False:

Assuming there exists a language $A$ such that: $ (VC≀_P A) \land (\overline{A} ≀_P IS) $ then NP is closed under complement

When trying to prove it is true I tried to use the following theorem:

$L\in NPComplete \land L\in coNP β†’ 𝑁𝑃 = π‘π‘œπ‘π‘ƒ β†’ NP$ is closed under complement

My attempt:

We know both VC and IS are NPComplete problems, which implies from the reductions that:

$A \in \text{NP-Hard}$ and $\overline{A}\in NP$

the only thing missing is $A\in NP$ for satisfying the condition: $A\in NPComplete \land A\in coNP$ and reaching the conclusion: $NP=coNP$

What am I missing?

$\endgroup$

1 Answer 1

0
$\begingroup$

ok apparently $\overline{IS}$ is also $NPComplete$ which means $A \in NP$ and we already know from the reduction that $A\in \text{NP-Hard}$ which mean $A\in NPComplete$

we also know that $\overline{A}\in NP$

$β†’A\in NPComplete \land A\in coNP β†’ NP=coNP β†’$ NP is closed under complement

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