In:
ACM SIGACT News, Association for Computing Machinery (ACM), Vol. 28, No. 2 ( 1997-06), p. 2-13
Abstract:
This issue's column surveys recent progress in raising NP-hardness lower bounds to parallel NP lower bounds. Complexity theorists will learn that Lewis Carroll (unbeknownst to himself) was a fellow complexity theorist. So that readers specializing in algorithms don't feel left out, let me mention that they are in even better company. Algorithms for apportioning the US House of Representatives were designed and debated by Adam, Hamilton, Jefferson, Webster, and other famous figures from American history, as recounted in a page-turner by Balinski and Young ([BY82]; see also [BY85] for a shorter take and [HRSZ96] for a more explicitly computational spin). Looking forward, the next issue's column will be a survey, by Mitsunori Ogihara, of DNA-based computing.
Type of Medium:
Online Resource
ISSN:
0163-5700
DOI:
10.1145/261342.261344
Language:
English
Publisher:
Association for Computing Machinery (ACM)
Publication Date:
1997
detail.hit.zdb_id:
1133944-5
detail.hit.zdb_id:
243806-9
detail.hit.zdb_id:
2043299-9
