多项式时间、指数时间复杂性类和Tally集  

作　　者：李宏宙[1] 

机构地区：[1]华南师范大学计算机科学系,广州510631

出　　处：《科学通报》1995年第3期278-279,共2页Chinese Science Bulletin

基　　金：国家"八六三"高科技;云南省应用基础基金资助项目

摘　　要：可计算复杂性类之间的差异和联系是结构复杂性理论中主要研究的问题,而多项式时间复杂性类P和NP与指数时间复杂性类E和NE之间的关系更加引人注目.众所周知:如果P=NP,则E=NE.但反过来是否有:如果E=NE,则P=NP,仍是一个未解决问题.有多种途径试图解决这个问题.Book证明了:E=NE当且仅当在NP-P中不存在Tally集;Hartmanis等证明了:E=NE当且仅当在NP-P中不存在稀疏集(sparse set),这就是著名的向上分离结果(upward-separation result).此外是相对化的应用,到目前为止。

关 键 词：多项时间 指数时间复杂性 Tally集 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]