1
$\begingroup$

I'm working on the following problem:

HALFCYCLE (HALFC):

Input:

A directed graph $G = (V,E)$.

Output:

Whether the longest cycle in $G$ has length $ \lfloor |V|/2 \rfloor$.

Prove that if $\mathsf{PH} \ne \mathsf{coNP}$ then HALFCYCLE is not NP-complete.

I have no idea how to solve this implication.

$\endgroup$
0
$\begingroup$

Show that if HALFCYCLE is NP-complete then $\mathsf{NP}=\mathsf{coNP}$, and so the polynomial hierarchy collapses to NP.

How do you prove that if HALFCYCLE is NP-complete then $\mathsf{NP}=\mathsf{coNP}$? There are two options:

  1. Show that coSAT reduces to HALFCYCLE. Since HALFCYCLE is NP-complete, in particular it is in NP, and so coSAT is in NP, implying NP=coNP.
  2. Show that HALFCYCLE is in coNP. Since HALFCYCLE is NP-hard, in particular SAT reduces to HALFCYCLE, and so SAT is in coNP, implying NP=coNP.

(You can replace SAT with any NP-hard problem, and coSAT with any coNP-hard problem.)

Good luck!

$\endgroup$
  • $\begingroup$ Thanks for your help Yuval Filmus. :) I'll try to solve it. $\endgroup$ – Stefano Ferraro Jun 14 at 14:18
  • $\begingroup$ Well, by choosing the first option and using the exercise 3, claim 2 in the following link cse.iitkgp.ac.in/~abhij/course/theory/CC/Spring04/ct2Sol.pdf, in theory, it should be enough to prove NP = co-NP. Are you agreeing with me? $\endgroup$ – Stefano Ferraro Jun 14 at 15:31
  • $\begingroup$ Part of doing math is realizing when you have proved something. $\endgroup$ – Yuval Filmus Jun 14 at 16:18

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.