Provable Reductions in TFNP

Noah Fleming, Stefan Grosser, Toniann Pitassi +1

We introduce a new family of propositional proof systems, denoted <EF, R>, for an arbitrary TFNP search problem $R$. Informally, a refutation of a CNF formula $F$ in <EF, R> is giv…