On Pigeonhole Principles and Ramsey in TFNP

Siddhartha Jain, Jiawei Li, Robert Robere +1

We show that the TFNP problem RAMSEY is not black-box reducible to PIGEON, refuting a conjecture of Goldberg and Papadimitriou in the black-box setting. We prove this by giving red…