Extremal combinatorics, iterated pigeonhole arguments, and generalizations of PPP
Extremal combinatorics, iterated pigeonhole arguments, and generalizations of PPP
复制标题
极值组合、迭代鸽笼论证以及 PPP 的推广
DOI：
10.48550/arxiv.2209.07625
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Christos Papadimitriou
中科院分区：
文献类型：
--
作者：
Amol Pasarkar;M. Yannakakis;Christos Papadimitriou
我们研究极值组合学中存在性定理所产生的计算问题的复杂性。对于这些问题中的一些，基于鸽子洞原理的迭代应用，保证存在解决方案。这导致在TFNP中定义了一个新的复杂性类，我们称之为PLC（“多项式长选择”）。PLC包括所有的PPP，以及许多以前未分类的总体问题，包括与拉姆齐定理，向日葵定理，Erd\H{o}s-Ko-Rado引理和K\“onig引理有关的搜索问题。这四个问题中的前两个是否是PLC完全的是一个重要的开放问题，我们追求的，相比之下，我们表明，后两个PPP完全。最后，我们将PPP重新定义为一个优化问题，并定义了一个与Tur\'an定理相关的层次结构。
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\H{o}s-Ko-Rado lemma, and K\"onig'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\'an's theorem.