# Are "almost all" decidable languages not in P?

There's a famous classical circuit complexity result by Shannon that says almost all languages require exponential circuits [[1]], proven by comparing the number of distinct circuits of $$n$$ variables versus the number of boolean functions of $$n$$ variables.

Similarly, there's a result that "almost all" languages are undecidable, because the set of TMs is countable while the set of languages is uncountable.

Question: is there a result of similar flavor about complexity classes? E.g. something like "almost all" decidable languages are not in P?

The question seems interesting to me because it's much less clear how to even define "almost all". Both sets here are countably infinite so cardinality arguments don't work. We could maybe do something like $$\lim_{n \to \infty} \frac{\text{# of polytime TMs with n states}}{\text{# of total TMs with n states}}$$ ? But that's obviously tremendously complicated and out of reach. Are there simpler definitions that would capture a similar meaning?

• Writing this made me realize: <# of polytime TMs with n states> might not capture what I want because many TMs can decide the same language. I know there's a computable enumeration of decidable languages. Is there an enumeration of decidable languages without duplication? Nov 25, 2022 at 20:58
• If you enumerate all decidable languages in some particular order, so that $L_n$ is the nth language, then you can consider $\lim_n (\text{# of languages }L_k\text{ in P, with }k\leq n)/n$. But it will be very strongly dependent on the order, and it will be hard to argue that the order you chose is not arbitrary.
– Stef
Nov 26, 2022 at 9:58
– cody
Nov 28, 2022 at 18:16
• Worth noting that unlike most computability issues, this is absolutely going to depend on your encoding of TMs.
– cody
Nov 28, 2022 at 18:17

So my intuition would say no, there sre no more decidable problems not in P than the problems in $$P$$, since you can reduce a problem $$L$$ of running time $$O(f(n))$$ into a problem $$L’=\{w0^{f(|w|)}|w\in L\}$$ in $$P$$, i.e. we add many zeros to each instance, to make the size of the input large enough, that the original algorithm has linear running time on the resulting instance.
Note also that such a reduction is not really interesting (we can’t really use it to make any complexity assumptions about membership of $$P$$) since the reduction itself is not computable in log space and it is not even in FTIME(g(n)) for any computable g, since you can always choose a harder problem to begin with.
• You are right, I still have no full answer. One difference though is that there we can fix n and count the number of n-ary functions and n-ary functions with slightly super polynomial running time and compare them. So maybe a first step for a yes answer is to find the right definition of $\lim_n$. Nov 26, 2022 at 10:35