P. M. Long and M. K. Warmuth.
Composite geometric concepts and polynomial
predictability. Information
and Computation, 113(2):203-252, 1994. (Available in Postscript and PDF formats.)
Abstract
We study the predictability of geometric concepts,
in particular those defined by boolean combinations of
simple geometric objects.
First, we give a negative result,
showing that the problem of predicting the class of
convex polytopes encoded by
listing their vertices
is prediction complete for P.
Thus, an efficient solution to
this prediction problem
implies the existence of efficient solutions to all prediction problems whose associated
evaluation problems are in P.
Assuming the existence of a one-way function
that is hard on iterates, there are
such prediction problems
which do not admit efficient solutions.
Thus we show under minimal cryptographic
assumptions that the class of
convex polytopes encoded by
listing their vertices is not predictable. As a side
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 reductions.
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 predictable.
Finally, we give an Occam algorithm for predicting fixed finite unions of
boxes. Both constructive results
for flats and boxes hold if the dimension is variable.