# Logarithmic reduction from Clique to Half-Clique

so the question is in the title basically but I am now studying for a Complexity Theory Exam and encountered this problem in the exercises. I understand how to make a poly-reduction but I am not able to wrap my head around how to do it in logarithmic space.

The question itself is as follows

Show that $$Clique \leq_L Half-Clique.$$ any help would be appreciated!

I am adding the definitions for comfort purposes: $$Clique = (G,k) : G \ is\ a\ graph\ that\ has\ a\ clique\ of\ size\ k$$ $$Half-Clique = G : G \ is\ a\ graph\ that\ has\ a\ clique\ of\ size\ |V|/2$$

• How does your poly-time reduction go? Where does it fail to be logspace? – dkaeae Jul 24 at 12:35
• My reduction is to take the given clique and basically copy the graph without its edges to create a 2|V| sized graph. Then I continue to connect from the copied part $|V|-k$ nodes to the original clique group in order to change its size from $k$ to $|V-k+k|$ which is half the size of the graph and therefore is half-clique. – David Jul 24 at 12:56