Large Clique is in P or NP-complete? P != NP for hypothesis I need to find a solution to the following question: The problem to find a "Large Clique" is in P or NP-complete (assuming P != NP)? The "Large Clique" problem is the following: Given a graph G = (V, E), does it contain a clique of size at least |V |/2? I was thinking to use the relationship between the problem to find a clique in G by using the problem to find a Vertex Cover on the complement graph. What do you think, could it be the right approach?

According to Garey and Johnson, _Computers and Intractability_ , page 194, CLIQUE is NP-complete, and "the variant in which, for a given $r$, $0\lt r\lt1$, we are asked whether $G$ contains a clique of size $r|V|$ or more is NP-complete for any fixed value of $r$."