The Medvedev lattice is a mathematical framework for comparing the difficulty of computational problems, specifically problems that involve finding points in certain well-behaved sets called effective closed sets. Think of these sets as collections of infinite sequences that can be described by a computer program. The Medvedev lattice arranges these sets into a hierarchy based on reducibility: one set is "easier than or equal to" another if there is a computable procedure that transforms solutions of the harder problem into solutions of the easier one. Sets that are equally difficult in this sense share the same "degree." The lattice has been a useful tool in logic and computability theory, but this paper asks a different kind of question: how hard is it to use the lattice itself?
Specifically, the authors study the computational complexity of determining whether a given effective closed set belongs to the same degree as some fixed reference set. This is a question about a question, sometimes called a meta-complexity problem. They show that for almost all degrees in the lattice, this membership problem is as hard as it could possibly be within a natural complexity class, meaning no shortcuts exist. Interestingly, the argument for this result is not one-size-fits-all; it depends on a new property the authors define called "self-similarity" of a degree, which roughly captures whether the set folds back on itself in a structured way.
The one exception that requires special treatment is the hardest possible degree, the top of the lattice. Pinning down the exact complexity in that case turns out to be genuinely difficult, and the authors can only establish a lower bound that comes close to but does not quite match the known upper bound, leaving a small open gap. They also analyze a related question: how hard is it to decide whether a given set is incomparable in difficulty to a fixed reference degree, meaning neither is reducible to the other? They prove this problem reaches its maximum possible complexity whenever the reference degree sits strictly between the bottom and top of the lattice.