An Ancient Combinatorial Problem. Issue 6 (31st May 2022)
- Record Type:
- Journal Article
- Title:
- An Ancient Combinatorial Problem. Issue 6 (31st May 2022)
- Main Title:
- An Ancient Combinatorial Problem
- Authors:
- Berger, Marc
Winkler, Peter - Abstract:
- Abstract: We study a 2000-year-old combinatorial problem which may be the first NP-complete problem in history. The Mishna considers two versions of the problem, giving an elegant solution to the first (amounting to a pseudo-polynomial algorithm), but only a partial solution to the second. We finish the job by giving a complete solution to the second problem as well as to a common generalization of the two, concluding that all three problems are weakly NP-complete.
- Is Part Of:
- American Mathematical Monthly. Volume 129:Issue 6(2022)
- Journal:
- American Mathematical Monthly
- Issue:
- Volume 129:Issue 6(2022)
- Issue Display:
- Volume 129, Issue 6 (2022)
- Year:
- 2022
- Volume:
- 129
- Issue:
- 6
- Issue Sort Value:
- 2022-0129-0006-0000
- Page Start:
- 566
- Page End:
- 575
- Publication Date:
- 2022-05-31
- Subjects:
- Mathematics -- Periodicals
510.5 - Journal URLs:
- https://www.tandfonline.com/loi/uamm20 ↗
http://www.tandfonline.com/ ↗ - DOI:
- 10.1080/00029890.2022.2073780 ↗
- Languages:
- English
- ISSNs:
- 0002-9890
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 21772.xml