patternMinor
Decidable languages unconditionally not in P/poly
Viewed 0 times
languagesdecidableunconditionallypolynot
Problem
What are some nice/natural examples of languages not contained in $P/\mathit{poly}$, preferably decidable ones?
I'm interested in unconditional results rather than examples such as the Karp–Lipton theorem, which states that SAT is not in $P/\mathit{poly}$ unless the polynomial hierarchy collapses.
I'm interested in unconditional results rather than examples such as the Karp–Lipton theorem, which states that SAT is not in $P/\mathit{poly}$ unless the polynomial hierarchy collapses.
Solution
Let $H_{f(n)}$ be the set of all pairs $(M,x)$ such that $M$ halts on $x$ within $f(|x|)$ steps. We encode the pairs in such a way that $|(M,x)| = |x| + C_M$, where $C_M$ is a constant that depends only on $M$. Suppose that $H_{f(n)}$ has circuits of size $g(n)$ (note that it's a slightly different $n$).
Let $h(n) \leq \kappa 2^n/n$, for an appropriate $\kappa > 0$.
Let $M_{h(n)}$ be the Turing machine which on input $x$ of length $n$ generates all $n$-input circuits of size at most $h(n)$, determines the lexicographically first truth table of an $n$-bit function $\Phi_{n,h(n)}$ which is not generated by this circuit (such a function exists due to our assumption on $h(n)$), halts if $\Phi_{n,h(n)}(x) = 1$, and enters an infinite loop otherwise. By construction, $\Phi_{n,h(n)}$ cannot be computed by a circuit of size $h(n)$ or less.
The running time of $M_{h(n)}$ on an input of length $n$ is $O(2^{h(n) + n})$, hence if we choose $f(n) \geq K 2^{h(n) + n}$ for an appropriate constant $K > 0$, we can compute $\Phi_{n,h(n)}$ using a circuit of size $g(n + C_{M_{h(n)}}) + O(1)$. This shows that for some constant $C>0$, $g(n + C_{M_{h(n)}}) + C > h(n)$.
Given $f(n)$, the best choice for $h(n)$ is $\min(\log_2 f(n) - n - K',\kappa 2^n/n)$, where $K'$ is some constant. This implies the following result, which holds for some constant $C'$.
Theorem. Suppose that for all $D>0$ there exists $n$ such that $\min(f(n),2^{\kappa 2^n/n}) \geq 2^{g(n + D) + n + C'}$. Then $H_{f(n)}$ cannot be computed by circuits of size $g(n)$ or smaller.
In particular, $H_{2^{r(n)}}$ doesn't have polynomial size circuits whenever $r(n)$ is super-polynomial. On the other hand, $H_{2^{r(n)}}$ can be computed in time roughly $O(2^{r(n)})$.
(This is essentially the argument of Jeřábek in this answer.)
Let $h(n) \leq \kappa 2^n/n$, for an appropriate $\kappa > 0$.
Let $M_{h(n)}$ be the Turing machine which on input $x$ of length $n$ generates all $n$-input circuits of size at most $h(n)$, determines the lexicographically first truth table of an $n$-bit function $\Phi_{n,h(n)}$ which is not generated by this circuit (such a function exists due to our assumption on $h(n)$), halts if $\Phi_{n,h(n)}(x) = 1$, and enters an infinite loop otherwise. By construction, $\Phi_{n,h(n)}$ cannot be computed by a circuit of size $h(n)$ or less.
The running time of $M_{h(n)}$ on an input of length $n$ is $O(2^{h(n) + n})$, hence if we choose $f(n) \geq K 2^{h(n) + n}$ for an appropriate constant $K > 0$, we can compute $\Phi_{n,h(n)}$ using a circuit of size $g(n + C_{M_{h(n)}}) + O(1)$. This shows that for some constant $C>0$, $g(n + C_{M_{h(n)}}) + C > h(n)$.
Given $f(n)$, the best choice for $h(n)$ is $\min(\log_2 f(n) - n - K',\kappa 2^n/n)$, where $K'$ is some constant. This implies the following result, which holds for some constant $C'$.
Theorem. Suppose that for all $D>0$ there exists $n$ such that $\min(f(n),2^{\kappa 2^n/n}) \geq 2^{g(n + D) + n + C'}$. Then $H_{f(n)}$ cannot be computed by circuits of size $g(n)$ or smaller.
In particular, $H_{2^{r(n)}}$ doesn't have polynomial size circuits whenever $r(n)$ is super-polynomial. On the other hand, $H_{2^{r(n)}}$ can be computed in time roughly $O(2^{r(n)})$.
(This is essentially the argument of Jeřábek in this answer.)
Context
StackExchange Computer Science Q#144850, answer score: 2
Revisions (0)
No revisions yet.