PUB - Publikationen an der Universität Bielefeld

The monotonicity checking problem is a sorting-type problem defined as: Given a finite poset and an unknown real-valued function on it, find out whether this function is order preserving. We investigate the worst case behaviour of decision monotonicity checking algorithms. Two models are considered: the comparison model and the linear model. In the comparison model the queries are pairwise comparisons of values of the function. We get some general bounds on monotonicity checking complexity and analyse the dependence of the complexity of monotonicity checking on certain type of combinatorial operations on posets. We determine the monotonicity checking complexity of the ranked poset in which every two elements of different rank are comparable and get nontrivial lower and upper bounds on the complexity of monotonicity checking of the Boolean lattice. Also, we investigate monotonicity checking of functions that take a "small" number of different values and determine the monotonicity checking complexity of Boolean functions. The queries in this model are comparisons of linear combinations of the values of the input function. We consider a geometric interpretation of monotonicity checking and give a method for establishing lower bounds on the complexity of monotonicity checking in the linear model using this interpretation. We use this method to establish a lower bound on the monotonicity checking complexity of a particular poset. As a consequence, we get a lower bound on the complexity of simultaneous determination of the minimum and the maximum of a sequence of real numbers.