Search versus Decision for $\mathsf{S}_2^\mathsf{P}$
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908687775301632 |
|---|---|
| author | Fortnow, Lance |
| author_facet | Fortnow, Lance |
| contents | 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 $Σ_2^p \cap Π_2^p$ is contained in ZPP^NP. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_02808 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Search versus Decision for $\mathsf{S}_2^\mathsf{P}$ Fortnow, Lance Computational Complexity 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 $Σ_2^p \cap Π_2^p$ is contained in ZPP^NP. |
| title | Search versus Decision for $\mathsf{S}_2^\mathsf{P}$ |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2512.02808 |