Abstract of Paper

Reducing the Number of Solutions of NP Functions
by Lane Hemaspaandra, Mitsunori Ogihara, and Gerd Wechsung

Abstract:

We study whether one can prune solutions from NP functions.  Though it is
known that, unless surprising complexity class collapses occur, one cannot
reduce the number of accepting paths of NP machines (Ogihara, M., and
Hemachandra, L.A., Journal of Computer and System Sciences, volume 46, pages
295--325, 1993), we nonetheless show that it often is possible to reduce the
number of solutions of NP functions. For finite cardinality types, we give a
sufficient condition for such solution reduction.  We also give absolute and
conditional necessary conditions for solution reduction, and in particular
we show that in many cases solution reduction is impossible unless the
polynomial hierarchy collapses.