1
$\begingroup$

This is just a question for fun and specifically for those who have read the reference pervasively.

I have been reading the work of Knuth's The Art of Computer Programming and struggling and having a lot of fun with its exercises. I was very impressed that Fermat's Last Theorem had a difficulty of 45 in Knuth's difficulty scale.

I was wondering, if anyone of you have seen exercises with rank ≥50.

Perhaps a more interesting question, what is the current status of such problems nowadays!?

$\endgroup$
  • 1
    $\begingroup$ I think this is too broad in its current form. You seem to ask for many things: there are presumably several hard problems, each with their current status, whatever that might mean exactly. $\endgroup$ – Juho Sep 21 '15 at 19:17
  • $\begingroup$ @Juho I don't think that a question about the ratings of exercises within a particular series of books is overly broad. $\endgroup$ – David Richerby Sep 21 '15 at 20:11
  • 1
    $\begingroup$ @DavidRicherby I think I still disagree. If you already know there is a problem with difficulty 45, why not look at the book(s) yourself, and find out exactly the set of problems that are interesting, and ask specific questions about those problems? Well, let's let the community decide. $\endgroup$ – Juho Sep 21 '15 at 20:13
  • 2
    $\begingroup$ user2820579, We expect you to make a significant effort before asking. So why don't you look through the book yourself and compile a list of all exercises with rank ≥50? This isn't a place to outsource a task like that. (And then once you've done that, you could ask a specific question about the current status of one of those.) $\endgroup$ – D.W. Sep 21 '15 at 21:10
  • 1
    $\begingroup$ Fermat's Last Theorem was 50 in early editions, until some student hired for proofreading found a proof that was too short to fit on the margins of the book. Sorry, until Wiles proved it. $\endgroup$ – gnasher729 Sep 30 '17 at 21:07
5
$\begingroup$

Knuth's scale goes up to 50 (for "unsolved research problems"). Note that the scale is meant to be (roughly) logarithmic, i.e., adding 10 to the number multiplies the work required by a factor, with 50 meaning some so ridiculously large amount of work to be done that it can be taken practically as "infinite".

Fermat's Last Theorem used to be 50 as an example in the preface, with Wiles' proof it is now "just" extremely hard, i.e., it got demoted to 45 in later editions.

So the answer to the question is "no". By definition 50 is the highest value on the scale.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The question asks if there's something "with rank ≥50". That's not excluded by definition of the scale going up to 50. $\endgroup$ – David Richerby Sep 21 '15 at 20:08
  • $\begingroup$ @DavidRicherby, by Knuth's definition the top is 50. It used to be the rating of Fermat's Last Theorem for a reason. $\endgroup$ – vonbrand Sep 22 '15 at 0:52
  • 1
    $\begingroup$ OK, I'm confused. You say, "The answer to the question is 'no'." I assume the question you mean is whether there's an exercise with rating greater than or equal to 50. Knuth's definition is that every question has a question less than or equal to 50. So Knuth's definition alone does not imply that the answer is no: a question rated exactly 50 is possible. $\endgroup$ – David Richerby Sep 22 '15 at 6:41
  • $\begingroup$ I think maybe an $e^\frac{1}{50-x}$ would be a better rough estimation then. $\endgroup$ – peterh - Reinstate Monica Feb 1 '17 at 12:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.