苏盛辉 2025-02-16
《Theoretical Computer Science
(TCS)》(图1)创刊于1975年，由Elsevier出版，是理论计算机科学领域期刊的翘楚。
相对于2010年的0.86，其目前0.9的影响因子似乎不算太高且增长缓慢(这是其偏向理论、刊文较多、读者群体较稳定的缘故)，但在理论计算机科学类期刊中已是较高的了。
其至少刊登有两篇图灵奖贡献论文：
(1) The Complexity of Computing the
Permanent，作者Leslie Gabriel Valiant，1979年(图2)。
(2) NP Is As Easy As Detecting Unique
Solutions，一作Leslie Gabriel Valiant，1986年(图3)。
论文1论述了积和式计算的复杂性，并首次提出了#P(Sharp-P)问题类(图4)。积和式计算是典型的计数问题(Counting
<或Enumeration> Problem)。
论文2论述了区分无解单一解代数难题实例或找到代数难题实例唯一解是同该难题一样困难的。强调了适合密码学的NP问题是存在的。
两篇论文的作者L. G.
Valiant正是因为在计数复杂性、代数计算复杂性等方面的贡献而获得2010年的图灵奖[图5-6]。
加载中，请稍候......
(2025-02-16 21:26:21) 
加载中…