Recognition of order-preserving maps (Q1063048)

Let P, Q be finite ordered sets and \(f: P\to Q\) be a monotone mapping. For a given algorithm A whose elementary steps are the evaluations of f on elements of P let \(\phi\) (A,f) be the number of steps of A which are necessary to know f. Further, put \(\phi (P,Q)=\min \max \phi (A,f)\); the maximum taken over all f's and minimum over all algorithms A. The author finds lower bounds and upper bounds for the number \(\phi\) (P,Q) and determines this number exactly in some special cases.