论文标题
极端组合学，迭代的鸽洞论点和PPP的概括
Extremal combinatorics, iterated pigeonhole arguments, and generalizations of PPP
论文作者
论文摘要
我们研究了由极端组合学中存在定理引起的计算问题的复杂性。对于这些问题中的某些问题，确保根据Pigonhole原理的迭代应用来确保存在解决方案。这导致了TFNP中新的复杂性类别的定义，我们称之为PLC（用于“多项式长期选择”）。 PLC包括所有PPP，以及许多先前未分类的总问题，包括与Ramsey的定理有关的搜索问题，The向日葵定理，Erdős-Ko-Rado Lemma和König的Lemma。这四个问题中的前两个是否是PLC完成是我们提出的一个重要的公开问题。相比之下，我们表明后两个是PPP完整的。最后，我们将PPP重新定义为一个优化问题，并定义了与Turán定理相关的此类问题的层次结构。
We study the complexity of computational problems arising from existence theorems in extremal combinatorics. For some of these problems, a solution is guaranteed to exist based on an iterated application of the Pigeonhole Principle. This results in the definition of a new complexity class within TFNP, which we call PLC (for "polynomial long choice"). PLC includes all of PPP, as well as numerous previously unclassified total problems, including search problems related to Ramsey's theorem, the Sunflower theorem, the Erdős-Ko-Rado lemma, and König's lemma. Whether the first two of these four problems are PLC-complete is an important open question which we pursue; in contrast, we show that the latter two are PPP-complete. Finally, we reframe PPP as an optimization problem, and define a hierarchy of such problems related to Turán's theorem.
