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.
We are given as inputs subsets over a universe .
We must accept updates of the following kind: Given a pointer to two subsets and , create a new subset .
After each update, we must output whether the new subset is empty or not.