The Collapse of the Polynomial Hierarchy: NP = P (A Summary)

Details The Collapse of the Polynomial Hierarchy: NP = P (A Summary) The Collapse of the Polynomial Hierarchy: NP = P (A Summary)

2008-12-07

arxiv.org/abs/0812.1385v11

Computer Science

Computational Complexity

v11: This is a short version of the full paper in v9. Reorganized Section 4. Total 7 pages including 4 figures

Scientific paper

We present a novel extension to the permutation group enumeration technique which is well known to have polynomial time algorithms. This extended technique allows each perfect matching in a bipartite graph on 2n nodes to be expressed as a unique directed path in a directed acyclic graph on O(n^3) nodes. Thus it transforms the perfect matching counting problem into a directed path counting problem for directed acyclic graphs. We further show how this technique can be used for solving a class of #P-complete counting problems by NC-algorithms, where the solution space of the associated search problems spans a symmetric group. Two examples of the natural candidates in this class are Perfect Matching and Hamiltonian Circuit problems. The sequential time complexity and the parallel (NC) processor complexity of counting all the solutions to these two problems are shown to be O(n^{19}\log(n)) and O(n^{19}) respectively. And thus we prove a result even more surprising than NP = P, that is, #P = FP, where FP is the class of functions, f: \{0, 1\}* --> N, computable in polynomial time on a deterministic model of computation such as a deterministic Turing machine or a RAM. It is well established that NP \subseteq P^{#P}, and hence the Polynomial Time Hierarchy collapses to P.

Affiliated with

Also associated with

No associations

Rating

The Collapse of the Polynomial Hierarchy: NP = P (A Summary) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Collapse of the Polynomial Hierarchy: NP = P (A Summary), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Collapse of the Polynomial Hierarchy: NP = P (A Summary) will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-450292