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

博文

我们对The P versus NP 问题的突破性研究成果

已有 4112 次阅读 2017-2-7 20:21 |系统分类:科研笔记|关键词:学者


 经过多年的积累沉淀,特别是最近半年多的深思熟虑,我对the P versus NP问题形成了新的突破性理解和结论:NP-complete problems(NP完全问题)可以进一步分类,而并非传统认为的一个大类。我们发现NPC问题在计算复杂度上并不相同,可以从它们的特性,规约方法,准确解等方面进行细分,从而为找到更高效的解决NPC问题的方法、为解决P vs NP问题提供了借鉴。


Title1: NP Complete Problems Are Not Equivalent

http://www.scholat.com/portalPaperInfo.html?paperID=31472&Entry=tianwenhong

Abstract: NPComplete (abbreviated as NPC) problems, standing at the crux of deciding whether P=NP, are among thehardest problems in computer science and other related areas. Through decades, NPC problems are treated as one class. Our  intensive study shows that NPC problems are not all equivalent in computational complexity, and they can be further classified. We then  show that the classification of NPC problems may depend on their reduction methods,exact algorithms, natures, and the boundary between P and NP. Finally we discuss about the NPC problems in real-life and shine some lights on finding better solutions to NPC problems.


 该论文已于2017年放在arxiv并投稿ACM审稿中。


Title 2:  On the Transformability of P and NP problems

http://www.scholat.com/portalPaperInfo.html?paperID=31472&Entry=tianwenhong

Abstract:  In this paper, we show a new perspective: P and NP problems can be mutually transformable. We provide a concise proof for this theory.

提供了一种P 与 NP 问题互相转换的定理及证明方法,为探讨the P and NP problem提供了新思路。

 该论文已于2017年2月10日投稿。



https://m.sciencenet.cn/blog-1028294-1032181.html

上一篇:一切指望, 都在实验室里的人

5 姜咏江 马省伟 雷蕴奇 刘钢 yangb919

该博文允许注册用户评论 请点击登录 评论 (2 个评论)

数据加载中...

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

GMT+8, 2022-9-28 08:05

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部