2 papers
cs.CC2026
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 . Informally, a refutation of a CNF formula in <EF, R> is giv…
cs.CC2025
Total Search Problems in
Noah Fleming, Stefan Grosser, Siddhartha Jain +4
We initiate a systematic study of , the class of total search problems solvable by polynomial time randomized algorithms. contains a variety o…