A Meta Theorem for Σ2P-Completeness in Fewest Clues Problems

We study the Fewest Clues Problem (FCP), a framework that asks whether fixing parts of a certificate forces uniqueness for problems in NP. While several FCP versions of NP-complete problems are known to be Σ2P-complete, a general method has been lacking. We present a meta theorem: if P is NP-complete and FCP-P is Σ2P-complete, then any parsimonious reduction (i.e., preserves the number of solutions by a one-to-one correspondence between solutions) from P to Q whose certificates satisfy a simple alignment (each target coordinate is either a constant or an injective image of exactly one source coordinate) implies that FCP-Q is Σ2P-complete. As a case study, we prove that FCP-Minesweeper Consistency Problem (FCP-MCP) is Σ2P-complete: first by a direct parsimonious reduction adapted from the classical MCP construction, and second by verifying that the same reduction meets the meta theorem's conditions. To make the method practical, we add a short “cookbook” checklist and work out two additional instantiations beyond MCP: FCP POSITIVE PLANAR 1-IN-3 SAT and FCP 1-IN-3 SAT+. Our theorem thus provides a systematic route to transfer Σ2P-completeness once a suitable parsimonious, certificate-aligned reduction is available.