论文标题
Wordle是NP-HARD
Wordle is NP-hard
论文作者
论文摘要
Wordle是一个单人猜测游戏，目标是发现从字典$ d $中选择的秘密单词$ w $。为了发现$ w $，玩家最多可以制作$ \ ell $猜测，这也必须是$ d $的单词，$ d $中的所有单词都具有相同的长度$ k $。每次猜测之后，都会通知玩家他们的猜测与秘密单词相匹配的位置，以及在秘密单词中出现在不同位置的字母中。我们从复杂的角度研究了词游戏，证明了其自然形式化的NP硬度：如果玩家可以保证在$ \ ell $ upeces中发现秘密单词，则决定给定字典$ d $和整数$ \ ell $。此外，我们证明，即使在单词具有长度$ k = 5 $的情况下，硬度也存在，即使在这种情况下，即使在这种情况下，也可以近似保证发现秘密单词所需的最小猜测数量。我们还提出了有关其参数化复杂性的结果，并提供了一些相关的开放问题。
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 $w$, the player can make at most $\ell$ 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 positions in which their guess matches the secret word, as well as letters in the guess that appear in the secret word in a different position. We study the game of Wordle from a complexity perspective, proving NP-hardness of its natural formalization: to decide given a dictionary $D$ and an integer $\ell$ if the player can guarantee to discover the secret word within $\ell$ guesses. Moreover, we prove that hardness holds even over instances where words have length $k = 5$, and that even in this case it is NP-hard to approximate the minimum number of guesses required to guarantee discovering the secret word. We also present results regarding its parameterized complexity and offer some related open problems.
