yhu的个人博客分享 http://blog.sciencenet.cn/u/yhu

博文

NP=P被证明了?难道又一个数学难题被攻破?

已有 8334 次阅读 2008-4-1 01:18 |个人分类:未分类

 去年在网上看论文,无意看见这篇,当时还没有发,挂在arxiv上,不过已经有很多评论.今天又看了一下,作者修改过几次,已经在几个地方发了.不知道这个是不是真地被证明了.

Equality of complexity classes P and NP: Linear programming formulation of the quadratic assignment

problemMoustapha Diaby

Abstract: In this paper, we present a polynomial-sized linear programming formulation of the Quadratic Assignment Problem (QAP). The proposed linear program is a network flow-based model. Hence, it provides for the solution of the QAP in polynomial time. Computational testing and results are discussed.
Comments: 6 pages; Published in the 2006 IMECS Conference Proceedings (ISBN: 988 98671-3-3); Hofman's claimed "counter-example" is invalid: violates set of constraints 2.10
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM)
ACMACMACMACMACMACMACMACM classes: F.2.2
Cite as: arXiv:cs/0609004v9 [cs.CC]
Equality of complexity classes P and NP

https://wap.sciencenet.cn/blog-40109-20067.html

上一篇:个人的科学品味
下一篇:国内学者多写点SCI的文章有什么不对?
收藏 IP: .*| 热度|

0

发表评论 评论 (4 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-3-29 06:39

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部