Reducing the number of solutions of NP functions

DOI10.1006/JCSS.2001.1815MaRDI QIDQ1608321zbMATH OpenOpenAlexFDO

Authors Lane A. Hemaspaandra, Ogihara, Mitsunori, Gerd Wechsung

Publication date 4 August 2002

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcss.2001.1815

cardinality reduction computational path function refinement narrowing-gap condition non-deterministic polynomial time NP functions NP machines solution reduction

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

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.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Reducing the number of solutions of NP functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1608321)