You probably think Wordle, the game all the bright people seem to be playing, is a mental challenge. But did you know it was hard.. NP hard?

You almost certainly know what Wordle is - and in case you've been under a rock recently it's a web-based word game created and developed by Welsh software engineer Josh Wardle in October 2021 and snapped up by the New York Times within a matter of months. Just the sort of success developers dream of.

But did you imagine that it is NP Hard?

If you know what NP and NP Hard are all about skip this basic introduction to the ideas:

We characterise the difficulty of problem by how long it takes to solve as the size of the problem increases. Some problems are easy in the sense that the time that they take to solve doesn't go up too much as the size of the problem increases. Some problems are hard in the sense that the time it takes increases rapidly - exponentially as the problem gets bigger.

Problems that are NP are those that are difficult to solve but easy to check. For example, to find a route that visits 100 towns and is less than X miles then you have no choice but to search all of the possible ways of getting around them. The algorithm takes exponential time as the number of towns increases. This makes the problem difficult to solve. But if you are given a route that is less than X miles in total you can check it very quickly in a time that is proportional to the number of towns. So this problem is hard to solve but easy to check. 

Problems that are hard to solve but easy to check are known as NP for Nondeterministic Polynomial. The name comes from the idea that if you can guess a solution - i.e. nondeterministic - you can check it in polynomial time.

Problems that are NP Hard aren't NP themselves but if you can solve them in a given time then you can solve NP problems in the same sort of time. That is NP Hard problems are at least as difficult as NP problems and if you can find a fast solution to an NP Hard problem you can create a fast solution to NP problems. This would mean that you have solved the $1 million prize problem and have proved that P=NP  i.e. that NP problems are not just easy to check but easy to solve.

As a result NP Hard problems are of great interest but there are lots of them and proving that a given problem is NP Hard is a common enough occurence. However, given the interest in Wordle the fact that it is NP Hard is a fun observation. Here is the mathematical definition of Wordle from the paper by Bernardo Subercaseaux, a PhD student at Carnegie Mellon and Daniel Lokshtanov, professor of Computer Science at University of California Santa Barbara, that proves it NP Hard:

Wordle is a single player word-guessing game where the goal is to discover a secret word w that has been chosen from a dictionary D. In order to discover the w, the player can make at most l guesses, which must also be words from D, all words in D having the same length k. After each guess, the player is notified of the position in which their guess matches the secret word, as well as the letters in the guess that appear in the secret word in a different position.

Recognize it?

The question about Wordle that is NP hard is "how many guesses are needed to guarentee solving the problem". In this case the number of letters in the problem isn't restricted in and you might think that this is the cause of the difficulty. However the paper goes on to present the result that even if you fix k at five, which is the standard size of a Wordle problem, then putting a figure on the minimum number of guesses required is NP Hard.

That Wordle is NP hard might not be a surprise if you have tried it, but notice that it is the task of specifying the number of guesses needed that is NP hard, not the problem itself. However it is proven that even for k=5 Wordle cannot be solved in polynomial time.

• Mike James is the author of The Programmer’s Guide To Theory which sets out to present the fundamental ideas of computer science in an informal and yet informative way and devotes a chapter to a discussion of what makes a problem NP-hard.

More Information

Wordle is NP-hard  Daniel Lokshtanov, Bernardo Subercaseaux

Related Articles

Eight Queens Solved!

N Queens Completion Is NP Complete

Rubik's Cube Is Hard - NP Hard

Column Subset Selection Is NP-complete

Unshuffling A Square Is NP-Complete

NP-Complete - Why So Hard?

NP Complete

Classic Nintendo Games Are NP Hard

Physics Is NP Hard

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info