0
$\begingroup$

how proof ${\ \ NPC \ \ \bigcap \ \ CO-NPC \ne \varnothing }$
then ${NP = P ? }$

$\endgroup$
  • 2
    $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX). $\endgroup$ – D.W. Jan 4 at 18:23
  • 2
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in asking better questions. $\endgroup$ – D.W. Jan 4 at 18:40
1
$\begingroup$

I don't think you're likely to find any such proof. Given our current level of knowledge, as far as we know it is possible that $\textsf{P} \ne \textsf{NP}$ but $\textsf{NP} = \textsf{co-NP}$ (we cannot prove otherwise). If that were true, then we'd have $\textsf{NPC} = \textsf{co-NPC}$ (and thus $\textsf{NPC} \cap \textsf{co-NPC} \ne \emptyset$) yet $\textsf{P} \ne \textsf{NP}$.

See, e.g., Is the open question NP=co-NP the same as P=NP? and If NP $\neq$ Co-NP then is P $\neq$ NP.

| cite | improve this answer | |
$\endgroup$

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.