NP完全性理论新进展：大卫·约翰逊的专栏回顾

需积分: 9 40 浏览量更新于2024-07-17 收藏 233KB PDF 举报

《NP完全性列》是大卫·约翰逊（David Johnson）在ACM Transactions on Algorithms上发表的一系列文章，作为AT&T实验室的计算机科学家，他在这篇专栏中探讨了NP完全性理论的新进展。该文章承袭了1979年迈克尔·雷蒙德·盖瑞（M.R. Garey）和约翰逊在《计算复杂性：NP完全性理论指南》（Computers and Intractability: A Guide to the Theory of NP-Completeness）一书中的研究模式，该书简称“[G&J]”。此前的23期专栏，每期都是在《J. Algorithms》上发布，如“[Col1,1981]”表示第一期发表于1981年。这一期的专栏旨在回顾该系列的历史与初衷，以及对《G&J》和先前专栏中提出的开放问题的最新进展。主要内容集中在以下几个方面： 1. **NP完全性概述**：阐述了NP完全性的概念，这是一种复杂性理论中的重要类别，标志着一类问题的困难程度，即它们至少与已知最难以解决的问题——如旅行商问题或图论中的3-SAT问题——一样难。理解NP完全性对于确定算法效率至关重要，因为任何能在多项式时间内解决NP完全问题的算法都将改变计算机科学的基石。 2. **历史和目的**：约翰逊解释了他为何选择这个主题进行长期研究，以及这些文章如何随着时间的推移反映了NP完全性理论的发展脉络，包括新发现的NP完全问题、证明复杂性和算法改进等。 3. **开放问题的更新**：重点关注《G&J》中列出的未解决难题，比如判定一个整数是否为质数（primality testing）和寻找完美图（perfect graphs），这仍然是当前理论研究的热点。每期专栏都可能包含对这些问题的新视角、部分解答或者更深入的理解。 4. **算法分析和问题复杂性**：讨论了如何通过复杂性类之间的关系、可约性（reducibility）和完备性来分析算法的性能，以及如何将这些理论应用到实际问题中。 5. **术语和关键词**：文章使用了通用术语“算法”，强调理论分析，并且提到了“NP完全性”和“开放问题”这两个核心关键词，以及与之相关的“primality testing”和“perfect”。《NP完全性列》不仅是一份关于理论研究的深度探讨，也是一部反映NP完全性领域动态的编年史，对于理解和跟进计算机科学的前沿理论具有重要意义。读者可以从中了解到最新的研究成果和尚未破解的理论挑战，对于研究人员和学生来说，这是一个宝贵的学习资源。

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 “eﬃciently 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 eﬃcient 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

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

log n log log n), the running time for the

Adleman-Huang algorithm is O(n

) 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) veriﬁed 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

NP完全性理论新进展：大卫·约翰逊的专栏回顾

COMPUTERS AND INTRACTABILITY： A Guide to the Theory of NP-Completeness

Computer And Intractability - A Guide To The Theory Of NP-Completeness

np-completeness：应付NP-completeness

The Theory of NP-Completeness

A Guide to the Theory of NP-Completeness

Computers and Intractability - A Guide to the Theory of NP-Completeness

Computers and Intractability_A Guide to the Theory of NP-Completeness

Computers and Intractability: A Guide to the Theory of NP-Completeness

NP-completeness of the Active Time Scheduling Problem_活动时间调度问题的N

Data Structures and Algorithms (Vol 2. Graph Algorithms and NP-Completeness)

最新资源