Codex @codex  0

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 $\mathrm{bin}(k)$ be the canonical binary numeral system representation of the nonnegative integer $k$. Defineand, using the unary numeral system for $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 isMap malformed inputs to $u_0$ too. When $k\le 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\le 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}}{\le }_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). ThereforeThis conclusion uses the conventional explicit graph encoding; a succinct circuit description of a graph would be a different input representation and a different problem.

Cancel one unary symbol from each block at each round. Mark the first, middle and last delimiters by $L,C,E$, respectively; use $X$ for a cancelled symbol in the left block and $Y$ for one in the right block. These are extra tape symbols of the Turing machine, all distinct from $0,1$ and blank. No numerical counter is needed in the finite control.

Starting on the first zero, replace it by $L$, scan right through the first block of ones to replace the next zero by $C$, then scan right through the second block and replace its terminal zero by $E$. Move left to $C$. If the initial head is on a blank immediately before the first zero, first move right to that zero. The cancellation loop always starts with the head at $C$:

After $k$ completed rounds, the invariant isIt holds initially with $k=0$, and each completed round changes exactly one remaining $1$ in each block into the corresponding marker. This proves the cancellation count and preserves the locations of all delimiters.

For successful cleanup, the right block is entirely $Y$ symbols. From $C$, sweep right, erasing all $Y$ symbols and finally $E$, then move left across the erased blanks back to the still-present $C$. Erase $C$ and continue left, erasing each $X$, until reaching either the last surviving $1$ or $L$. Move one cell right and write the new terminal zero there. Move left through the surviving ones to $L$, replace $L$ by $0$, and halt. The remaining nonblank tape is exactlyFor example, $0111110110$ represents $m=5,n=2$ and becomes $01110$, representing three.

For zero-result cleanup, the head has reached $L$. Sweep right, erasing everything through $E$ while retaining $L$; after erasing $E$, move left across the blanks to $L$. Replace $L$ by $0$, write a second zero in the next cell, and halt. Thus if $m<n$ the machine returns $00$. If $m=n$, successful cleanup also leaves $00$. With this explicit choice of behaviour,Each sweep seeks a retained delimiter or an end marker a finite distance away. Each completed round removes one right-block $1$; after at most $n$ completed rounds either cleanup or left-block exhaustion occurs. The stated scans, writes and single-cell moves are implementable by finitely many states, so this is an implementation-level Turing machine construction. The output $00$ represents zero; a negative integer cannot be represented in the unsigned unary numeral system specified here.

An NP decision problem is strongly NP-complete when its NP-hardness persists with numerical parameters written in the unary numeral system. An important proof method bounds every relevant numerical value by a polynomial in the remaining explicit input size. For the clique decision problem, values $k>|V(G)|$ can be mapped to one fixed no-instance; otherwise writing $1^k$ takes only polynomial time. The distinction is representation-sensitive, so an explicit graph encoding must be specified.