The Status of the P versus NP Problem.
The article refers to a 1971 research paper by Steve Cook, "The Complexity of Theorem-Proving Procedures" and focuses on computational complexity. The Polynomial Time (P) versus Nondeterministic Polynomial-Time (NP) problem in computer science is discussed, as well as the theory of efficient algorit...
| Published in: | Communications of the ACM Vol. 52; no. 9; pp. 78 - 87 |
|---|---|
| Main Author: | |
| Format: | Article |
| Published: |
Association for Computing Machinery
Sep2009
|
| Subjects: | |
| Online Access: | View this record in EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=44181661&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 44181661 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00010782 ACM jtl: Communications of the ACM issn: 00010782 maglogo: N pubinfo: dt: Sep2009 vid: 52 iid: 9 pid: 68 pub: Association for Computing Machinery artinfo: ui: 44181661 10.1145/1562164.1562186 ppf: 78 ppct: 9 formats: tig: atl: The Status of the P versus NP Problem. aug: au: FORTNOW, LANCE affil: Professor of Electrical Engineering and Computer Science at Northwestern University's Mccormick School of Engineering, Evanston, Il. su: NP-complete problems Computational complexity Computational mathematics Polynomials Proof theory Algorithms sug: subj: NP-complete problems Computational complexity Computational mathematics Polynomials Proof theory Algorithms ab: The article refers to a 1971 research paper by Steve Cook, "The Complexity of Theorem-Proving Procedures" and focuses on computational complexity. The Polynomial Time (P) versus Nondeterministic Polynomial-Time (NP) problem in computer science is discussed, as well as the theory of efficient algorithms for a solution to NP-complete problems. Integer programming, approaches to proving that P≠NP such as diagonalization, circuit and proof complexity with Boolean operators, brute force and heuristics, NP-complete optimization and the limits of approximation, hardness assumptions in cryptography, and the elimination of randomness are mentioned. pubtype: Periodical doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2009 holdings: @attributes: islocal: N |
|---|