TR96-027 Authors: Lane A. Hemaspaandra, Ashish Naik, Mitsunori Ogihara, Alan L. Selman

Publication: 26th March 1996 20:51

Downloads: 670

Keywords:

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.