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$$

  • 2
    $\begingroup$ How does your poly-time reduction go? Where does it fail to be logspace? $\endgroup$ – dkaeae Jul 24 at 12:35
  • $\begingroup$ 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. $\endgroup$ – David Jul 24 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.