38 citations · 73 across the 10 of their papers we have counts for
3 papers · 1 filter
Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
Marcelo Arenas, María Alejandra Schild, Bernardo Subercaseaux
We introduce a new elementary technique for proving -hardness results under Turing reductions, and showcase its applicability by settling the counting complexity of several fu…
Wordle is NP-hard
Daniel Lokshtanov, Bernardo Subercaseaux
Wordle is a single-player word-guessing game where the goal is to discover a secret word that has been chosen from a dictionary . In order to discover , the player can ma…
The Computational Complexity of Evil Hangman
Jérémy Barbay, Bernardo Subercaseaux
The game of Hangman is a classical asymmetric two player game in which one player, the setter, chooses a secret word from a language, that the other player, the guesser, tries to d…