Hardness of a special GAP-CLIQUE problem
The problem is solvable in polynomial time, using the following algorithm:


  Keep removing pairs of unconnected vertices, until a clique remains.


If the graph has a clique of size $(3/4)n$, then the clique you end up with contains at least $n/4$ vertices (exercise).

Source: Boppana and Halldórsson, Alon and Kahale.