Christos H. Papadimitriou – Communications of the ACM

Opinion Sep 1 2012

A personal account of Alan Turing's life and impact.

Author Archives

Research and Advances Feb 1 2009

The Complexity of Computing a Nash Equilibrium

Traditionally, computational problems fall into two classes: those that have a polynomial-time algorithm and those that are NP-hard. However, the concept of NP-hardness cannot be applied to the rare problems where "every instance has a solution."

Systems and Networking

illustration of Nash's function for the penalty shot game

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved