Meta Theorem for Hardness on FCP-Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908322141044736 |
|---|---|
| author | Nagao, Atsuki Sekiguchi, Mei |
| author_facet | Nagao, Atsuki Sekiguchi, Mei |
| contents | 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 \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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_11859 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Meta Theorem for Hardness on FCP-Problem Nagao, Atsuki Sekiguchi, Mei Computational Complexity 68Q15 F.1.3 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 \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. |
| title | Meta Theorem for Hardness on FCP-Problem |
| topic | Computational Complexity 68Q15 F.1.3 |
| url | https://arxiv.org/abs/2504.11859 |