Talk:Computers and Intractability

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 What should I do? 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. If the image is non-free then you may need to provide a fair use rationale If the image isn't freely licensed and there is no fair use rationale, then it cannot be uploaded or used. If the image has already been deleted you may want to try Deletion Review This notification is provided by a Bot --CommonsNotificationBot (talk) 00:45, 26 November 2011 (UTC)

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)