Computing Solutions Uniquely Collapses the Polynomial Hierarchy
Authors:
- Lane A. HemaspaandraLHLane A. Hemaspaandra
- Ashish V. NaikANAshish V. Naik
- Mitsunori OgiharaMOMitsunori Ogihara
- Alan L. SelmanASAlan L. Selman
- 1 August 1996
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 25 (4) , 697-708
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 ${\text{ZPP}}^{{\text{NP}}} $ (and thus, in particular, to ${\text{NP}}^{{\text{NP}}} $). Because 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 semirecursive 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 {\text{NP}}$ is NPSV-selective, then $A \in {{({\text{NP}} \cap {\text{coNP}})} / {{\text{poly}}}}$. Relatedly, we prove that if $A \in {\text{NP}}$ is NPSV-selective, then A is ${\text{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.
Keywords
This publication has 30 references indexed in Scilit:
- On collapsing the polynomial-time hierarchyInformation Processing Letters, 1994
- Semi-membership algorithmsACM SIGACT News, 1994
- On using oracles that compute valuesLecture Notes in Computer Science, 1993
- Threshold computation and cryptographic securityLecture Notes in Computer Science, 1993
- Lower bounds for the low hierarchyJournal of the ACM, 1992
- Strong and robustly strong polynomial-time reducibilities to sparse setsTheoretical Computer Science, 1991
- Complexity Measures for Public-Key CryptosystemsSIAM Journal on Computing, 1988
- Sparse Sets, Lowness and HighnessSIAM Journal on Computing, 1986
- Quantitative Relativizations of Complexity ClassesSIAM Journal on Computing, 1984
- Cryptocomplexity and NP-completeness1980