P3. In
"Discovering Auxiliary Information for Incremental Computation",
we proposed a approach for finding auxiliary information. Auxiliary
information is, by definition, useful information about x that
is not computed by f(x). Where, then, can one find it?
The key insight of this approach is:
- A. Consider, as candidate auxiliary information
for f, all intermediate computations of an incremental version
of f that depend only on x; such an incremental version
can be obtained using some techniques we developed for solving P1 and
P2. (We use techniques developed for solving P1 and P2, instead of
just P1, so that the candidate auxiliary information includes
auxiliary information useful for efficiently maintaining the
intermediate results.)
How can one discover which pieces of candidate auxiliary
information are useful and how they can be used? We proposed:
- B. Extend f with all candidate auxiliary
information, then apply some techniques used in our methods for P1 and
P2 to obtain an extended version and an incremental extended version
that together compute, exploit, and maintain only useful intermediate
results and useful auxiliary information.