Refutation of Aslam's Proof that NP = P

Details Refutation of Aslam's Proof that NP = P Refutation of Aslam's Proof that NP = P

2009-04-24

arxiv.org/abs/0904.3912v2

Computer Science

Computational Complexity

13 pages, 2 figures, a response to Aslam's paper (arXiv:0812.1385v11) and the underlying arguments (arXiv:0812.1385v9). Very m

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Refutation of Aslam's Proof that NP = P 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 Refutation of Aslam's Proof that NP = P, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Refutation of Aslam's Proof that NP = P will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-609750