# Complexity of “half cycle”

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.

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!

• Thanks for your help Yuval Filmus. :) I'll try to solve it. – Stefano Ferraro Jun 14 at 14:18
• 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? – Stefano Ferraro Jun 14 at 15:31
• Part of doing math is realizing when you have proved something. – Yuval Filmus Jun 14 at 16:18