COMPOSITE GEOMETRIC CONCEPTS AND POLYNOMIAL PREDICTABILITY

We study the predictability of geometric concepts, in particular those defined by boolean combinations of simple geometric objects. First, w e give a negative results, showing that the problem of predicting the class of convex polytopes encoded by listing their vertices is predict ion complete for P. Thus, an efficient solution to this prediction pro blem implies the existence of efficient solutions to all prediction pr oblems whose associated evaluation problems are in P. Assuming the exi stence of a one-way function that is hard on iterates, there are such prediction problems which do not admit efficient solutions. Thus we sh ow under minimal cryptographic assumptions that the class of convex po lytopes encoded by listing their vertices is not predictable. As a sid e effect, we show that determining membership in the convex hull of a given set of points is complete for P with respect to log space reduct ions. Next, we establish the predictability of the class consisting of unions of a fixed number of flats by reducing its prediction problem to that of the class of flats, which has previously been shown to be p redictable. Finally, we give an Occam algorithm for predicting fixed f inite unions of boxes. Both constructive results for flats and boxes h old if the dimension is variable. (C) 1994 Academic Press, Inc.