ECCC-Report TR96-027https://eccc.weizmann.ac.il/report/1996/027Comments and Revisions published for TR96-027en-usTue, 26 Mar 1996 20:51:14 +0300
Paper TR96-027
| Computing Solutions Uniquely Collapses the Polynomial Hierarchy |
Lane A. Hemaspaandra,
Ashish Naik,
Mitsunori Ogihara,
Alan L. Selman
https://eccc.weizmann.ac.il/report/1996/027Is there an NP function that, when given a satisfiable formula
as input, outputs one satisfying assignment uniquely? That is, can a
nondeterministic function cull just one satisfying assignment from a
possibly exponentially large collection of assignments? We show that if
there is such a nondeterministic function, then the polynomial hierarchy
collapses to ZPP$^{NP}$ (and thus, in particular, to NP$^{NP}$). As the
existence of such a function is known to be equivalent to the statement
``every NP function has an NP refinement with unique outputs," our result
provides the strongest evidence yet that NP functions cannot be refined.
We prove our result via a result of independent interest. We say that a
set $A$ is NPSV-selective (NPMV-selective) if there is a 2-ary partial NP
function with unique values (a 2-ary partial NP function) that decides
which of its inputs (if any) is ``more likely'' to belong to $A$; this is
a nondeterministic analog of the recursion-theoretic notion of the
semi-recursive sets and the extant complexity-theoretic notion of
P-selectivity. Our hierarchy collapse result follows by combining the
easy observation that every set in NP is NPMV-selective with the
following result: If $A$ in NP is NPSV-selective, then $A$ is in
(NP $\cap$ coNP)/poly. Relatedly, we prove that if $A$ in NP is
NPSV-selective, then $A$ is Low_2.
We prove that the polynomial hierarchy collapses even further, namely to
NP, if all coNP sets are NPMV-selective. This follows from a more general
result we prove: Every self-reducible NPMV-selective set is in NP.
Tue, 26 Mar 1996 20:51:14 +0300https://eccc.weizmann.ac.il/report/1996/027