All Questions
1 question
12
votes
1
answer
216
views
Reductions between languages of different densities?
The density of a language $X$ is a function $d_X \colon \mathbb{N} \to \mathbb{N}$ defined as $$d_X(n) = |\{x\in X \mid |x| \le n\}|.$$
Suppose $A$ and $B$ are languages over some finite alphabet, $A$ ...
- 19.2k