Total NP Search Problems with Abundant Solutions (Jiawei Li)


We define a new complexity class TFAP to capture TFNP problems that possess abundant solutions for each input. The canonical example of a TFAP problem is WeakPigeon --- finding a collision in a mapping from 2n pigeons to n holes. We build a general framework that separates TFAP with the rest of the TFNP world in the black-box setting. As a corollary, UEOPL is not in PWPP in the black-box setting.

Based on recent works: Total NP Search Problems with Abundant Solutions. To appear in ITCS-24.


2024-01-03  14:00 - 15:00   


Jiawei Li, UT Austin


Room 308