pith. sign in

arxiv: 0904.3912 · v2 · pith:YRZSVM2Pnew · submitted 2009-04-24 · 💻 cs.CC

Refutation of Aslam's Proof that NP = P

classification 💻 cs.CC
keywords algorithmaslammatchingsperfectbipartitecountgraphincomplete
0
0 comments X
read the original abstract

Aslam presents an algorithm he claims will count the number of perfect matchings in any incomplete bipartite graph with an algorithm in the function-computing version of NC, which is itself a subset of FP. Counting perfect matchings is known to be #P-complete; therefore if Aslam's algorithm is correct, then NP=P. However, we show that Aslam's algorithm does not correctly count the number of perfect matchings and offer an incomplete bipartite graph as a concrete counter-example.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.