Reducing the number of solutions of NP functions (Q1608321): Difference between revisions

By NP is denoted the set of all functions computable by nondeterministic polynomial-time Turing machines. These functions are known in the literature as NPMV (nondeterministic polynomial-time (potentially) multivariate) functions. In this paper, the problem whether NP functions can prune solutions away from NP functions is studied. In contrast to previous works that unless surprising complexity class collapses occur one cannot in general reduce even by one the number of accepting paths of NP machines, it is shown that the number of NP solutions can be reduced in various ways. A sufficient condition for the solution reduction is given in the case of finite cardinality types. Also the broad necessary conditions for solution reduction under the assumption that the polynomial hierarchy does not collapse are presented and it is proved an absolute necessary condition under which the solution cardinality can be pruned.