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$?


  • 7
    $\begingroup$ Well, PH is the closure of LinH under polytime reductions, hence $LinH\subseteq P/poly$ if and only if $PH\subseteq P/poly$. $\endgroup$ Jan 6, 2016 at 19:58
  • 1
    $\begingroup$ By strengthenings, we also have $\;\;\; NP\subseteq P/poly \: \implies \: PH = S_{\hspace{.02 in}2}\hspace{-0.03 in}P \:\:\:\:$. $\;\;\;\;\;\;\;\;\;$ $\endgroup$
    – user6973
    Jan 7, 2016 at 3:18


Your Answer

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