Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR96-027 | 20th February 1996 00:00

Computing Solutions Uniquely Collapses the Polynomial Hierarchy



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