REPORTS > DETAIL:

Paper:

TR96-027 | 20th February 1996 00:00

Computing Solutions Uniquely Collapses the Polynomial Hierarchy

TR96-027
Authors: Lane A. Hemaspaandra, Ashish Naik, Mitsunori Ogihara, Alan L. Selman
Publication: 26th March 1996 20:51
Keywords:

Abstract:

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

ISSN 1433-8092 | Imprint