A Characterization of Polynomial Time Enumeration (Collapse of the Polynomial Hierarchy: $\mathbf{NP = P}$)
Javaid Aslam · arXiv (Cornell University) · 2008
We resolve the $\mathbf{NP =P?}$ question by providing an existential proof to the following conjecture on the characterization of polynomial time enumeration: A sufficient condition for the existence of a P-time algorithm for any enumeration problem is the existence of a polynomially bounded partition hierarchy of the exponentially decreasing solution spaces, where each disjoint subset in each partition is P-time enumerable for each $n \ge 1$, n being the problem size. The existential proof is a P-time counting algorithm for perfect matchings, obtained by extending the basic enumeration technique for permutation groups to the set of perfect matchings in a bipartite graph. The sequential time complexity of this $\mathbf{\#P}$-complete problem is shown to be $O(n^{45}\log n)$. And thus we prove a result even more surprising than $\mathbf{NP = P}$, that is, $\mathbf{\#P}=\mathbf{FP}$, where $\mathbf{FP}$ is the class of functions, $f: \{0, 1\}^* \rightarrow \mathbb{N} $, computable in polynomial time on a deterministic model of computation such as a deterministic Turing machine or a RAM.