= Solution
To establish <strong NP-completeness>, use an explicit <adjacency matrix> encoding for a finite <simple graph>, with enough length information to recover its number $N$ of <vertices>. Let $\operatorname{bin}(k)$ be the canonical <binary numeral system> representation of the nonnegative <integer> $k$. Define
$$
\mathcal L_{\mathrm{Clique}}
=\{\langle\operatorname{enc}(G),\operatorname{bin}(k)\rangle:
G\text{ has a clique of size }k\},
$$
and, using the <unary numeral system> for $k$,
$$
\mathcal L_{u\mathrm{Clique}}
=\{\langle\operatorname{enc}(G),1^k\rangle:
G\text{ has a clique of size }k\}.
$$
The surrounding pairing syntax delimits the two components, so the empty unary field can encode $k=0$ if zero is included in the convention for <natural numbers>. Malformed descriptions are excluded from both <formal languages>.
Fix a unary no-instance $u_0$, for example one isolated <vertex> with requested size $2$. The <polynomial-time many-one reduction> is
$$
f(\langle\operatorname{enc}(G),\operatorname{bin}(k)\rangle)
=\begin{cases}
\langle\operatorname{enc}(G),1^k\rangle,&0\leq k\leq N,\\
u_0,&k>N.
\end{cases}
$$
Map malformed <inputs> to $u_0$ too. When $k\leq N$, only the numerical representation changes, so the existence of a $k$-<clique> is unchanged. When $k>N$, the original instance is false, since a <subset> of <vertices> cannot be larger than the whole <vertex set>; $u_0$ is false as required.
The important size bound is $k\leq N$ in the branch that writes $1^k$. The original explicit <graph> description already has length at least $N$, so the output has <polynomial> length and can be written in <polynomial time>. If a huge <binary numeral system> value $k$ is supplied, compare it with $N$ using its digit length and, when needed, a digit comparison; do not first allocate or print $k$ symbols. Merely replacing an unrestricted binary $k$ by $1^k$ would not be a valid <polynomial-time reduction>.
Thus $\mathcal L_{\mathrm{Clique}}\leq_p\mathcal L_{u\mathrm{Clique}}$. The unary version is in <NP> by the same <clique> <complexity certificate> verification, and is <NP-hard> by this <polynomial-time many-one reduction> and part (e). Therefore
$$
\boxed{\mathrm{Clique}\text{ is strongly NP-complete}.}
$$
This conclusion uses the conventional explicit <graph> encoding; a succinct circuit description of a <graph> would be a different <input> representation and a different problem.
Back to article page
