This question is about computing and maintaining the minimum of a set $S$ of integers while allowing updates on $S$.
The computation model we are considering is the unit-cost RAM machine with linear preprocessing. In this model, the power of the machine increases polynomially with the maximal allowed integer in the set to maintain. Formally, we have a constant integer $k$ such that, when maintaining a subset of $0, \dots, n$, each memory cell can store integers in the interval $-n^k, \dots, n^k$. Furthermore, operations on memory cells have unit cost, i.e., basic arithmetic operations (e.g., +, -, ×, /) on memory cells can be performed in constant time.
The goal of the problem is to maintain a set $S$ of integers, which is initially empty. The input to the problem is a sequence of operations that can be update operations (that modify the current set $S$) or query operations (asking a question about the current minimum of $S$); each operation must be processed before we receive the next operation. Formally, the possible updates are add($x$) to add $x$ to $S$ for $x\notin S$ (with $0 \leq x \leq n$), and remove($x$) to remove $x$ to $S$ for $x\in S$. The queries are defined below, and must always be posed at a point when $S$ is not empty. The complexity is measured in terms of the maximal time to process one operation. When measuring the complexity, we don't want to consider the special case where only few updates have been made, so we assume that at least $O(n)$ operations are updates and $O(n)$ operations are queries, where $n$ is the parameter of the machine (i.e., the largest number that the set $S$ can contain).
In problem 1, the queries simply ask for $min(S)$, the value of the minimal integer in $S$. It is easy to see that this version amounts to maintaining a priority queue, which we know from [1] to be equivalent to sorting integers. We have an $O( \log(\log(n)))$ algorithm (using a van Emde Boas tree) for this problem. But is a lower-bound known for this problem? Is it known that this cannot be maintained in constant time per operation?
In problem 2, the queries are Boolean: they have an input $t$ and the answer is either YES if $min(S)\leq t$ and NO otherwise. Clearly this variant is easier than problem 1, because knowning the value of the minimum allows us to compare it to any threshold given as input. Is anything known about the complexity of this problem (a better upper bound than problem 1, and/or a lower bound)? The problem seems to be the one dimension version of the dynamic half-space emptiness test, but we have not found any literature on this problem when the dimension is 1 (does it have a specific name?).
We would especially be interested in a lower bound showing that problem 1 cannot be maintained while spending (non-amortized) constant time on each operation, or an established complexity assumption claiming that this can't be done.
Reference
