Pagh's problem is a data structure problem often used when studying lower bounds in computer science named after Rasmus Pagh. Mihai Pătrașcu was the first to give lower bounds for the problem. In 2021 it was shown that, given popular conjectures, the naive linear time algorithm is optimal.
Definition We are given as inputs k {\displaystyle k} subsets X 1 , X 2 , … , X k {\displaystyle X_{1},X_{2},\dots ,X_{k}} over a universe U = { 1 , … , k } {\displaystyle U=\{1,\dots ,k\}} . We must accept updates of the following kind: Given a pointer to two subsets X 1 {\displaystyle X_{1}} and X 2 {\displaystyle X_{2}} , create a new subset X 1 ∩ X 2 {\displaystyle X_{1}\cap X_{2}} . After each update, we must output whether the new subset is empty or not.
References