PPP-Completeness and Extremal Combinatorics
summary
Paper proves PWPP corresponds to “weak” extremal theorems and PPP to “strong” ones, gives many new natural completions, and builds explicit reductions using the graph-hash product and lexicographic cover encodings. Main technical claims: implicit Ramsey and sunflower yield PWPP hardness, Weak-EKR maps shrinking circuits (alpha to alpha−2 bits) to collisions, and the tight Erdos–Ko–Rado bound (families larger than (2n−1 choose n−1) force disjoint sets) makes Erdos-Ko-Rado PPP-complete.
AI-written summary · about