Abstract:We compare the complexity of the search and decision problems for the complexity class S2P. While Cai (2007) showed that the decision problem is contained in ZPP^NP, we show that the search problem is equivalent to TFNP^NP, the class of total search problems verifiable in polynomial time with an NP oracle. This highlights a significant contrast: if search reduces to decision for S2P, then $\Sigma_2^p \cap \Pi_2^p$ is contained in ZPP^NP.
| Subjects: | Computational Complexity (cs.CC) |
| Cite as: | arXiv:2512.02808 [cs.CC] |
| (or arXiv:2512.02808v1 [cs.CC] for this version) | |
| https://doi.org/10.48550/arXiv.2512.02808 arXiv-issued DOI via DataCite |
Submission history
From: Lance Fortnow [view email]
[v1]
Tue, 2 Dec 2025 14:21:45 UTC (4 KB)