Provable Reductions in TFNP

Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere

We develop a new approach to implicit proof systems using white-box TFNP classes. In our new theory, an implicit proof can be viewed as a many-one reduction from the false-clause search problem associated with an unsatisfiable CNF formula to a problem in TFNP, coupled with an Extended Frege proof that the reduction is correct. Using this, we prove a new characterization of implicit Resolution, resolving an open problem posed by Krajicek.

To appear at ITCS 2027.

[PDF]