2025/04/16 by Nagao, Atsuki, Mei Sekiguchi, Sekiguchi, Mei
Computer Science · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Constraint Satisfaction and Optimization
paper · pdf · doi:10.48550/arxiv.2504.11859
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 ∈ \NP, its FCP variant is denoted by FCP-P. While several \NP-complete problems have been shown to have Σ2^\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 Σ2^\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 Σ2^\p-completeness of the FCP variants of several \NP-complete problems.