Meta Theorem for Hardness on FCP-Problem

The Fewest Clues Problem (FCP) framework has been introduced to study the complexity of determining whether a solution to an \NP~problem can be uniquely identified by specifying a subset of the certificate. For a given problem $P\in \text{NP}$, its FCP variant is denoted by FCP-$P$. While several \NP-complete problems have been shown to have ${\mathrm{\Sigma }}_2^{\text{p}}$-complete FCP variants, it remains open whether this holds for all \NP-complete problems. In this work, we propose a meta-theorem that establishes the ${\mathrm{\Sigma }}_2^{\text{p}}$-completeness of FCP-$P$ under the condition that the \NP-hardness of $P$ is proven via a polynomial-time reduction satisfying certain structural properties. Furthermore, we apply the meta-theorem to demonstrate the ${\mathrm{\Sigma }}_2^{\text{p}}$-completeness of the FCP variants of several \NP-complete problems.