Text Size
- Home
-
News
Advanced computing news from Communications of the ACM, other ACM resources, and from around the Web.
- Blogs
- Opinion
-
Browse by Subject
Recent articles from Communications organized into categories that encompass the broad scope of computing.
-
Magazine Archive
-
Careers
Jump-start your career with information on trends, opportunities and jobs – in both industry and academia.
- ACM Resources
-
Subscribe
Receive the benefits of ACM membership with a subscription to its flagship publication, Communications of the ACM.
Research highlights
The Complexity of Computing a Nash Equilibrium
![[article image]](/system/assets/0000/0266/012209_CACMp94_TheComplexity.large.jpg?1233000378&1233000377 "illustration of Nash's function for the penalty shot game")
An illustration of Nash's function for the penalty shot game.
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."
Tools For Readers
Text Size
Related ACM Resources
Conferences:
- ICDT 2012: 15th International Conference on Database Theory - March 26 – 29, 2012; Berlin, Germany
Courses:
- Project Communication Management - In this course, you will explore the communication planning processes and examine the inputs to and outputs from communication planning, information distribution, and performance reporting. (Duration: …
About Communications |
Join ACM 
|
Renew |
Subscribe |
Sign In |
For Authors |
For Advertisers |
Privacy |
Site Map |
Help |
Contact Us |
Mobile Site
Copyright © 2012 by the ACM. All rights reserved.