稀疏图灵归约“NP=P?”的关系

下载PDF

导出

摘要本文定义稀疏国灵归约，证明了定理：若NP（或PSPACE）有≤K-S-T-困难集，则NP=P（或P=PSPACE）．由此还获得了一些结果．

作者李芬兰

机构地区广西师范大学数学系

出处《计算技术与自动化》 1997年第1期4-8,共5页 Computing Technology and Automation

关键词稀疏集稀疏图灵归约计算复杂性理论

1刘春庆,戴跃伟,王执铨.抗主动攻击的隐秘通信方案[J].控制与决策,2004,19(2):191-194.
2张杰,周云才.计算复杂性类谱图[J].电脑知识与技术,2015,11(8X):40-42.
3赵子都.算法分析和计算复杂性理论[J].自动化博览,1998(3):43-46. 被引量：1
4胡运红.浅谈计算复杂性及其对运筹学发展的影响[J].运城学院学报,2009,27(2):13-16.
5吴琦.浅谈同态加密技术及其在物联网中的应用[J].通讯世界,2015,21(11):48-48. 被引量：2
6王则柯.数值方法计算复杂性理论的环境与进展[J].计算数学,1989,11(4):434-441. 被引量：3
7Avi Wigderson,刘宝光(译),叶其孝(校).P，NP和数学：计算复杂性透视[J].数学译林,2006,25(4):291-292.
8梅挺,代群,任伟.密码学中信息论及计算复杂性的研究[J].计算机工程与设计,2009,30(19):4393-4394.
9王立娜.美国计算机社区联盟发布白皮书明确人工智能六大待挖掘领域[J].世界科技研究与发展,2017,39(2):197-197. 被引量：1
10Chunping LIU,Yang ZHENG,Shengrong GONG.Image categorization using a semantic hierarchy model with sparse set of salient regions[J].Frontiers of Computer Science,2013,7(6):838-851.

计算技术与自动化

1997年第1期

浏览历史

内容加载中请稍等...