Refutation of Aslam's Proof that NP = P
| dc.creator | Ferraro, Frank | |
| dc.creator | Hall, Garrett | |
| dc.creator | Wood, Andrew | |
| dc.date | 2009-04-24 | |
| dc.date | 2009-05-14 | |
| dc.date.accessioned | 2026-07-07T13:14:43Z | |
| dc.date.available | 2026-07-07T13:14:43Z | |
| dc.description | 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. | |
| dc.description | 13 pages, 2 figures, a response to Aslam's paper (arXiv:0812.1385v11) and the underlying arguments (arXiv:0812.1385v9). Very minor content changes and typos fixed | |
| dc.identifier | https://arxiv.org/abs/0904.3912 | |
| dc.identifier | http://arxiv.org/abs/0904.3912 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/230260 | |
| dc.subject | Computational Complexity | |
| dc.subject | F.2.0; F.2.2 | |
| dc.title | Refutation of Aslam's Proof that NP = P | |
| dc.type | text |