𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Reducing the Number of Solutions of NP Functions

✍ Scribed by Lane A. Hemaspaandra; Mitsunori Ogihara; Gerd Wechsung

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
178 KB
Volume
64
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

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, 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.

📜 SIMILAR VOLUMES

On the Number of Solutions of Polynomial
On the Number of Solutions of Polynomial Systems
✍ M. Boguslavsky 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 247 KB

We consider systems of homogenous polynomial equations of degree d in a projective space ‫ސ‬ m over a finite field ‫ކ‬ q . We attempt to determine the maximum possible number of solutions of such systems. The complete answer for the case r ϭ 2, d Ͻ q Ϫ 1 is given, as well as new conjectures about th

Functions of Hydrotropes in Solutions
Functions of Hydrotropes in Solutions
✍ C. V. Subbarao; I. P. K. Chakravarthy; A. V. S. L. Sai Bharadwaj; K. M. M. Prasa 📂 Article 📅 2012 🏛 John Wiley and Sons 🌐 English ⚖ 203 KB 👁 1 views
Stability of the Shifts of a Finite Numb
Stability of the Shifts of a Finite Number of Functions
✍ Rong-Qing Jia 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 226 KB

Let , 1 , ..., , n be compactly supported distributions in L p (R s ) ( 0<p). We say that the shifts of , 1 , ..., , n are L p -stable if there exist two positive constants C 1 and C 2 such that, for arbitrary sequences a 1 , ..., a n # l p (Z s ), In this paper we prove that the shifts of , 1 , ..

On the number of positive solutions of e
On the number of positive solutions of elliptic systems
✍ Donal O'Regan; Haiyan Wang 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 178 KB

## Abstract The paper deals with the existence, multiplicity and nonexistence of positive radial solutions for the elliptic system div(|∇|^__p__ –2^∇) + __λk~i~__ (|__x__ |) __f^i^__ (__u__~1~, …,__u~n~__) = 0, __p__ > 1, __R__~1~ < |__x__ | < __R__~2~, __u~i~__ (__x__) = 0, on |__x__ | = __R__~1~