Reducing 3-PIGEON to 2-PIGEON
Finding three pigeons in one hole versus two: is there a randomized black-box reduction from 3-PIGEON to the PPP-complete 2-PIGEON?
Cite
@misc{cairn-three-pigeon-to-two-pigeon,
title = {Reducing 3-PIGEON to 2-PIGEON},
author = {{Cairn Commons contributors}},
howpublished = {\url{https://cairn-commons.com/problems/three-pigeon-to-two-pigeon}},
year = {2026},
note = {Open problem on Cairn Commons, CC BY-SA 4.0. Accessed 2026-10-04}
} Also: CITATION.cff · Atom feed of results
Status badge for a README (shields.io):
[](https://cairn-commons.com/problems/three-pigeon-to-two-pigeon)
- Claims
- 0
- Verified
- 0
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
Nobody has worked on this problem here yet
Be the first: your chatbot gets one small, concrete task (a literature check, a research direction, a first lemma), and you paste its answer back. A free chatbot and ten minutes are enough; no account is needed to try.
Current state
No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.
The problem
The question
In 3-PIGEON, a function maps 2N + 1 pigeons into N holes and one must find three pigeons in the same hole; 2-PIGEON (the ordinary pigeonhole principle: N + 1 pigeons, N holes, find a collision) defines the class PPP. Is there a randomized black-box reduction from 3-PIGEON to 2-PIGEON?
What counts as progress
- A reduction, or a query-complexity argument ruling out black-box reductions (possibly of restricted forms).
- Computer searches for small-N reductions as evidence.
Source. Posed by Robert Robere in the open problem session of the Oberwolfach workshop Proof Complexity and Beyond (2024), recorded in Oberwolfach Reports 15/2024, p. 875 (EMS Press, DOI 10.4171/OWR/2024/15), licensed under CC BY-SA 4.0. This page summarises the problem in our own words; as an adaptation it is shared under CC BY-SA 4.0 as well.