# Computational Complexity theory - Confusion about solving by reduction an NPC problem

I can't seem to grasp the term of reduction that well.

To explain I will take an example the problem of $$\sqrt{k} - clique$$ such that $$k \leq \sqrt{V}$$

Solving by reduction with normal k-clique such as $$k-clique \leq \sqrt{k}- clique$$

The reduction would be function f, such that f(G,k,) = (G',k') where the input is for K-clique.

The solution would be, to copy graph G to G' and add n^2-n individual nodes to G' leaving us with n^2 the size of G', hence we get that k' = k

Now what I what I want to understand is from the definition of reduction, does the normal k-clique algorithm works also on the graph G' in the output of function f? we only added to G, n^2-2 indiviual nodes that aren't connected to any edges, thus the number of clique nodes stays the same as k, coming from that we executed the algorithm of normal k-clique on the square root k clique? That's my understanding of reduction for now

• Can you define $\sqrt{k}$-clique formally? Also, in a reduction, you need to prove a statement of the form "The answer to instance $(G, k)$ is yes if and only if the answer to instance $f(G, k)$ is yes". Can you write what this statement is, concretely, for your problems? This can help clarifying. Jul 14, 2022 at 12:14
• @ManuelLafond Bare with me im newly adjusting to the term reduction. My question is similar to this post cs.stackexchange.com/questions/65014/… Jul 14, 2022 at 12:47