CACM logo

September 2009 (Vol. 52, No. 9)
The Status of the P versus NP Problem

Table of Contents

DEPARTMENT: Editor's letter

The Financial Meltdown and Computing

For many of us, the past year has been one of the most unsettling in our lifetime. In the late 1980s and early 1990s, we watched communism collapse of its own dead weight. In late 2008, we saw capitalism nearly crumble. Lehman …

Page 5

DEPARTMENT: Letters to the editor

Computer Science Does Matter

It was disappointing that two competent computer scientists — Matthias Felleisen and Shiram Krishnamurthi — took such a narrow view in their Viewpoint …

Pages 8-9

DEPARTMENT: In the Virtual Extension

In the Virtual Extension

Communications' Virtual Extension brings more quality articles to ACM members. These articles are now available in the ACM Digital Library.

Page 10

DEPARTMENT: BLOG@CACM

Saying Good-Bye to DBMSs, Designing Effective Interfaces

Michael Stonebraker discusses the problems with relational database management systems and possible solutions, and Jason Hong writes about interfaces and usable privacy and security.

Pages 12-13

DEPARTMENT: CACM online

What You Read on Your Summer Vacation

Here are the most popular articles and sections from the Communications site this past summer as indicated by our latest site statistics.

Page 14

COLUMN: News

Entering a Parallel Universe

The promise of parallel computing has run afoul of the harsh reality of Amdahl's Law, which puts a ceiling on the benefit of converting sequential code to parallel code. The upshot is that parallelism will not necessarily reap …

Pages 15-17

Medical Nanobots

Researchers working in medical nanorobotics are creating technologies that could lead to novel health-care applications, such as new ways of accessing areas of the human body that would otherwise be unreachable without invasive …

Pages 18-19

Facing an Age-Old Problem

Researchers are addressing the computing challenges of older individuals, whose needs are different — and too often disregarded.

Pages 20-22

Computer Science Meets Environmental Science

Scientists share knowledge and seek collaborators at computational sustainability conference.

Page 23

COLUMN: Viewpoints

Keeping Track of Telecommunications Surveillance

The creation of a statistical index of U.S. telecommunications surveillance activities and their results will benefit both civil liberties and law enforcement.

Pages 24-26

Computing: The Fourth Great Domain of Science

Computing is as fundamental as the physical, life, and social sciences.

Pages 27-29

How ICT Advances Might Help Developing Nations

Some predictions for technology developments, deployments, and the associated societal implications.

Pages 30-32

The Long Road to Computer Science Education Reform

Viewing the factors impeding improvements to CS education from kindergarten through grade 12 from a policy perspective.

Pages 33-35

Face the Inevitable, Embrace Parallelism

Hardware, software, and applications must all evolve in anticipation of the proliferation of parallelism.

Pages 36-38

An Interview with Maurice Wilkes

Maurice Wilkes, the designer and builder of the EDSAC — the first computer with an internally stored program — reflects on his career.

Pages 39-42

SECTION: Practice

Reveling in Constraints

The Google Web Toolkit is an end-run around Web development obstacles.

Pages 44-48

Monitoring and Control of Large Systems With MonALISA

MonALISA developers describe how it works, the key design principles behind it, and the biggest technical challenges in building it.

Pages 49-55

Making Sense of Revision-Control Systems

All revision-control systems come with complicated sets of trade-offs. How do you find the best match between tool and team?

Pages 56-62

SECTION: Contributed articles

Sound Index: Charts for the People, By the People

Mining the wisdom of the online crowds generates music business intelligence, identifying what's hot and what's not.

Pages 64-70

What Intellectual Property Law Should Learn from Software

Software's close encounters with the law provide some lessons for our future.

Pages 71-76

SECTION: Review article

The Status of the P Versus NP Problem

It's one of the fundamental mathematical problems of our time, and its importance grows with the rise of powerful computers.

Pages 78-86

SECTION: Research highlights

Abstraction for Parallelism

Looking for some new insight into an old problem? The  familiar problem of writing parallel applications and a fresh approach based on data abstraction allows some …

Page 88

Optimistic Parallelism Requires Abstractions

The problem of writing software for multicore processors is greatly simplified if we could automatically parallelize sequential programs. Although auto-parallelization has been studied for many decades, it has succeeded only

 …
Pages 89-97

They Do Click, Don't They?

You never click on advertisements received in spam or in phishing messages, do you? Nobody does. So, if that is true, why are we still getting an enormous amount of unsolicited …

Page 98

Spamalytics: An Empirical Analysis of Spam Marketing Conversion

Spam-based marketing is a curious beast. We all receive the advertisements — "Excellent hardness is easy!" — but few of us have encountered a person who admits to following through on this offer and making a purchase. And yet …

Pages 99-107

COLUMN: Last byte

Puzzled: Solutions and Sources

Last month (August 2009, p. 104) we posted a trio of brainteasers, including one as yet unsolved, concerning probability and intuition.

Page 110

Confusions of the Hive Mind

Be cautious about the artificial intelligence approach to computer science. It is impossible to differentiate the actual achievement of AI from the degree to which people change …

Pages 112-ff

SECTION: Virtual extension

Examining User Involvement in Continuous Software Development

Ms. Perez was giving a PowerPoint presentation to her potential clients in the hope of landing a big contract. She was presenting a new advertising campaign for a mutual fund company and had spent three months with her team on …

Pages 113-117

Constructive Function-Based Modeling in Multilevel Education

It is a digital age, especially for children and students who can be called the world's first truly digital generation. Accordingly a new generation education technology with a particular emphasis on visual thinking and specific …

Pages 118-122

One Size Does Not Fit All: Legal Protection for Non-Copyrightable Data

The web has become the largest data repository on the planet. An important factor contributing to its success is its openness and ease of use: anyone can contribute data to, and consume data from, the Web. As Tim Berners-Lee, …

Pages 123-128

The State of Corporate Website Accessibility

Web accessibility continues to have important social, legal and economic implications for ecommerce. Over 50 million Americans have disabilities and so do around 600 million world-wide (www.census.gov/prod/2003pubs/c2kbr-17.pdf …

Pages 128-132

Reducing Employee Computer Crime Through Situational Crime Prevention

Information security has become increasingly important for organizations, given their dependence on ICT. Not surprisingly, therefore, the external threats posed by hackers and viruses have received extensive coverage in the mass …

Pages 133-137

Ballot Box Communication in Online Communities

The participation of individual users in online communities is one of the most noted features in the recent explosive growth of popular online communities ranging from picture and video sharing (Flickr.com and YouTube.com) and …

Pages 138-142

Modified Agile Practices for Outsourced Software Projects

Frustration with the bureaucratic nature of the disciplined approach has led to the call for agile development. The new approach is defined by the Agile Manifesto (http://agilemanifesto.org/), which values individuals and interactions …

Pages 143-148

Falling into the Net: Main Street America Playing Games and Making Friends Online

In 1999, the National Telecommunications and Information Administration report Falling through the Net noted that "NTIA has found that there is still a significant "digital divide" separating American information "haves" andwidened …

Pages 149-150

About Communications | Join ACM External Link | Renew External Link | Subscribe External Link | Sign In | For Authors | For Advertisers External Link | Privacy | Site Map | Help | Contact Us

Copyright © 2009 by the ACM. All rights reserved.