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.
翻译:我们比较了复杂度类 S2P 中搜索问题与判定问题的复杂性。尽管 Cai(2007)证明了判定问题包含于 ZPP^NP 中,但我们发现搜索问题等价于 TFNP^NP,即一类可通过多项式时间验证且配备 NP 预言机的完全搜索问题类。这突显了一个显著对比:若 S2P 的搜索问题可归约至判定问题,则 $Σ_2^p \cap Π_2^p$ 将包含于 ZPP^NP 中。