Talk:Computers and Intractability
|This article is of interest to the following WikiProjects:|
File:Garey-johnson-79-cover.jpg Nominated for speedy Deletion
An image used in this article, File:Garey-johnson-79-cover.jpg, has been nominated for speedy deletion for the following reason: All Wikipedia files with unknown copyright status
Don't panic; you should have time to contest the deletion (although please review deletion guidelines before doing so). The best way to contest this form of deletion is by posting on the image talk page.
The twelve open problems
The list should not be in bold, per WP:SHOUT. Problem 11 is actually primality/compositeness testing, not factoring, and is thus solved. I'll also be adding some links and comments about updates from my copy, the 1982 second printing. Choor monster (talk) 14:03, 21 August 2015 (UTC)
Only two unsolved problems?
I dispute the uncited claim on the page that "As of 2015, only problem 1 has yet to be classified. Problem 12 is known to be NP-hard, but it is unknown if it is in NP."
For instance, consider the very recent paper of Levey and Rothvoss (arXiv preprint 1509.07808v1) which states that
"in fact, it is one of the remaining four open problems from the book of Garey and Johnson [GJ79] whether P3|prec,pj =1|Cmax is even NP-hard."
If you are unfamiliar with scheduling notation, the problem in question is exactly the one "Precedence constrained 3-processor scheduling" mentioned in the article. BöhmMartin (talk) 18:33, 6 October 2015 (UTC)