The complexity class TFNP contains all NP search problems where a solution is guaranteed to exist for every instance. A proof of totality is needed for every problem in TFNP, so syntactic subclasses (such as PLS, PPA, PPAD, PPP, and PWPP) categorize many problems in TFNP according to the argument needed for totality. Although these subclasses contain many natural complete problems, the status of whether all of TFNP can be solved efficiently remains unknown, specially noting that TFNP is unlikely to have a complete problem. Furthermore, it has been shown that hardness of TFNP cannot be based on P ̸= NP unless NP = coNP.

A major line of work has sought to base TFNP hardness on cryptographic assumptions. Existing positive results obtain hardness for subclasses of TFNP from cryptographic primitives such as one-way permutations, collision-resistant hashing, indistinguishability obfuscation, factoring, and various others. However, the status of basing the hardness on a general assumption such as the existence of one-way functions remains unsuccessful. There has been several attempts at providing evidence through black-box impossibility, the last of which − by Folwarczny, Goos, Hubacek, Maystre, and Yuan − shows that the impossibility for a restricted class of single-query reductions that are oblivious to the one-way function.

In this work, we provide full impossibility against reductions with an additional constraint. In particular, we allow the reduction to submit adaptive queries, with the caveat of restricting any submitted circuit to contain a single oracle gate.