4
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – nonagon
    Nov 25, 2022 at 20:58
  • 1
    $\begingroup$ 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. $\endgroup$
    – Stef
    Nov 26, 2022 at 9:58
  • $\begingroup$ See also: cs.stackexchange.com/q/155/988 and, more relevant: mathoverflow.net/a/71162/36103 $\endgroup$
    – cody
    Nov 28, 2022 at 18:16
  • $\begingroup$ Worth noting that unlike most computability issues, this is absolutely going to depend on your encoding of TMs. $\endgroup$
    – cody
    Nov 28, 2022 at 18:17

1 Answer 1

1
$\begingroup$

This answer relates to the number of decidable languages (and not the number of TMs that accept decidable languages).

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 that this is not a complete proof, but I would assume you can use this fact to build a proof.

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.

$\endgroup$
2
  • $\begingroup$ Hmm, thanks. On one hand this makes sense, on the other hand it kinda shows we might look for a better definition of "almost all". I believe the reduction you gave can also be applied in the circuit setting -- append zeros to a language to turn a non-poly circuit into poly. And yet, the theorem by Shannon still says something interesting about the nature of boolean circuits! $\endgroup$
    – nonagon
    Nov 26, 2022 at 4:59
  • $\begingroup$ 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$. $\endgroup$ Nov 26, 2022 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.