<p>By Karp-Lipton Theorem we have:
$$PH\subseteq P/poly\Rightarrow PH=\Sigma^p_2$$
So this theorem suggest it is unlikely that $PH\subseteq P/poly$.
I want to know is there any similar conditional or unconditional theorems that study relationship between $LinH$ and $P/poly$?</p>

<p>Thanks!   </p>

CC BY-SA 3.0
2016-01-06T19:58:40.043Z
Well, PH is the closure of LinH under polytime reductions, hence $LinH\subseteq P/poly$ if and only if $PH\subseteq P/poly$.
Emil Jeřábek
<cc.complexity-theory><complexity-classes><circuit-complexity><polynomial-hierarchy>
Linear Time Hierarchy and Circuit complexity
Erfan Khaniki
# Linear Time Hierarchy and Circuit complexity

(Asked by: username_0 on 2016-01-06)

By Karp-Lipton Theorem we have:
$$PH\subseteq P/poly\Rightarrow PH=\Sigma^p\_2$$
So this theorem suggest it is unlikely that $PH\subseteq P/poly$.
I want to know is there any similar conditional or unconditional theorems that study relationship between $LinH$ and $P/poly$?

Thanks!

**Tags:** cc.complexity-theory, complexity-classes, circuit-complexity, polynomial-hierarchy
> **Comments:**
> **username_1**: Well, PH is the closure of LinH under polytime reductions, hence $LinH\subseteq P/poly$ if and only if $PH\subseteq P/poly$.  

---

## 0 answers

