|
经过多年的积累沉淀,特别是最近半年多的深思熟虑,我对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日投稿。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-12-3 04:19
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社