# Constructing self-referential instances for the clique problem

arXiv: https://arxiv.org/abs/2601.19393 · HTML: https://mlsanity.com/paper/2601.19393/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jan 2026.

## Built on by (most cited first, 1 of 1)

- [Can Machines Really See Objects in Images? A Study Based on Syntactic Distance and Visual Self-Referential Instances](https://mlsanity.com/paper/2606.29416/) (2026)

## Abstract (arXiv)

In this paper, we propose constructing self-referential instances to reveal the inherent algorithmic hardness of the clique problem. First, we prove the existence of a phase transition phenomenon for the clique problem in the ErdHos--R'enyi random graph model and derive an exact location for the transition point. Subsequently, at the transition point, we construct a family of graphs. In this family, each graph shares the same number of vertices, number of edges, and degree sequence, yet both instances containing a k-clique and instances without any k-clique are included. These two states can be transformed into each other through a symmetric transformation that preserves the degree of every vertex. This property explains why exhaustive search is required in the critical region: an algorithm must search nearly the entire solution space to determine the existence of a solution; otherwise, a counterinstance can be constructed from the original instance using the symmetric transformation. Finally, this paper elaborates on the intrinsic reason for this phenomenon from the independence of the solution space.