4 · David Johnson
where the J. Algorithms webpage makes scanned .pdf copies of all the columns
available for a fee.
2. CLOSED AND ALMOST CLOSED PROBLEMS
In this section, I discuss the four open problems that have been resolved/partially
resolved since the last column appeared. Two turned out to be polynomial-time
solvable, and I’ll start with these. As we shall see, although the results represent
major theoretical breakthroughs, the running times for the discovered algorithms
represent yet another strong challenge to the notion that “polynomial-time solv-
able” is a synonym for “efficiently solvable in practice.”
COMPOSITE NUMBER [G&J]
instance: Positive integer N.
question: Are there positive integers p, q > 1 such that N = p · q?
Comment: The search for an efficient algorithm for this problem goes back at
least to 1801, when Gauss discussed it in his Disquisitiones Arithmeticae. When the
NP-Completeness Column went on hiatus in 1992, it was known that the problem
was unlikely to be NP-complete. The complementary problem PRIMES (is N a
prime?) was known also to be in NP [Pratt 1975], and no problem in NP ∩ co-NP
can be NP-complete unless the polynomial hierarchy PH collapses to NP. Also,
there was an algorithm of Adleman et al. [1983] that tests for primality in time
n
O(log log n)
, where n = dlog Ne is the length of the binary representation of N (the
input size). Such a running time would apply to all other NP-complete problems
if primality testing were NP-complete. (Given that COMPOSITE NUMBER is in
P if and only if PRIMES is in P, I shall for simplicity refer to the problem under
consideration as “primality testing” in what follows.)
Still more was known about primality testing in 1992. In particular, it had re-
cently been shown to be in ZPP, the set of all problems solvable in polynomial
time by Las Vegas algorithms: randomized algorithms that for each instance either
report the correct answer or say “I don’t know,” the latter occurring with proba-
bility less than 1/2. This followed from a result of Adleman and Huang [1992], who
adapted the elliptic curve approach of Goldwasser and Kilian [1986] to show that
primes could be recognized by a polynomial-time Monte Carlo algorithm: a ran-
domized algorithm that says “no” if the input is composite and says “yes” at least
half the time when the input is prime. The Las Vegas algorithm was obtained by
running this algorithm in parallel with one of the previously-discovered polynomial-
time Monte Carlo algorithms for recognizing composite numbers [Rabin 1976; 1980;
Solovay and Strassen 1978]. Unfortunately, although the Monte Carlo algorithms
for composite numbers run in time O(n
2
log n log log n), the running time for the
Adleman-Huang algorithm is O(n
30
) or worse (M.-D. Huang, personal communi-
cation, 2005). This means that the Las Vegas algorithm was far from practical,
although its mere existence led many to conjecture that primality testing is in P.
Ten years later, in a preprint that was released on the Internet on August 6, 2002,
and covered in The New York Times just two days later, Manindra Agrawal, Neeraj
Kayal, and Nitin Saxena (AKS) verified this conjecture. The preprint [Agrawal
et al. 2002] showed that primality testing is indeed in P, essentially by proving
ACM Transactions on Algorithms, Vol. V, No. N, Month 20YY.
剩余18页未读，继续阅读
刘金义
- 粉丝: 0
- 资源: 2
我的内容管理
展开
最新资源
- 计算机人脸表情动画技术发展综述
- 关系数据库的关键字搜索技术综述：模型、架构与未来趋势
- 迭代自适应逆滤波在语音情感识别中的应用
- 概念知识树在旅游领域智能分析中的应用
- 构建is-a层次与OWL本体集成：理论与算法
- 基于语义元的相似度计算方法研究：改进与有效性验证
- 网格梯度多密度聚类算法：去噪与高效聚类
- 网格服务工作流动态调度算法PGSWA研究
- 突发事件连锁反应网络模型与应急预警分析
- BA网络上的病毒营销与网站推广仿真研究
- 离散HSMM故障预测模型：有效提升系统状态预测
- 煤矿安全评价：信息融合与可拓理论的应用
- 多维度Petri网工作流模型MD_WFN：统一建模与应用研究
- 面向过程追踪的知识安全描述方法
- 基于收益的软件过程资源调度优化策略
- 多核环境下基于数据流Java的Web服务器优化实现提升性能
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
