Refutation of Aslam's Proof that NP = P
Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:YRZSVM2Precord.jsonopen to challenge →
classification
cs.CC
keywords
algorithmaslammatchingsperfectbipartitecountgraphincomplete
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.