2026-07-23T15:50:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19603 2024-03-06T11:04:27Z ddc:004 open_access

Total NP Search Problems with Abundant Solutions Li, Jiawei TFNP Pigeonhole Principle We define a new complexity class TFAP to capture TFNP problems that possess abundant solutions for each input. We identify several problems across diverse fields that belong to TFAP, including WeakPigeon (finding a collision in a mapping from [2n] pigeons to [n] holes), Yamakawa-Zhandry’s problem [Takashi Yamakawa and Mark Zhandry, 2022], and all problems in TFZPP. Conversely, we introduce the notion of "semi-gluability" to characterize TFNP problems that could have a unique or a very limited number of solutions for certain inputs. We prove that there is no black-box reduction from any "semi-gluable" problems to any TFAP problems. Furthermore, it can be extended to rule out randomized black-box reduction in most cases. We identify that the majority of common TFNP subclasses, including PPA, PPAD, PPADS, PPP, PLS, CLS, SOPL, and UEOPL, are "semi-gluable". This leads to a broad array of oracle separation results within TFNP regime. As a corollary, UEOPL^O ⊈ PWPP^O relative to an oracle O. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jiawei Li 2024 Is Part Of LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2024.75 urn:nbn:de:0030-drops-196031 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.75 eng https://creativecommons.org/licenses/by/4.0/legalcode