9
$\begingroup$

I believe the answers to this question give classes such that for all polynomials $p$,
there is a problem in the class which does not have circuits of size $p(n)$.
However, I'm asking about circuit size $\omega \hspace{.02 in}(n)$.

$\big(\hspace{-0.07 in}\left\langle \hspace{-0.04 in}0^{\hspace{.02 in}0}\hspace{-0.03 in},\hspace{-0.04 in}1^{\hspace{-0.03 in}1}\hspace{-0.03 in},2^{\hspace{.02 in}2}\hspace{-0.04 in},\hspace{-0.03 in}3^1\hspace{-0.04 in},\hspace{-0.03 in}4^4\hspace{-0.03 in},\hspace{-0.03 in}5^1\hspace{-0.04 in},\hspace{-0.03 in}6^{\hspace{.03 in}6}\hspace{-0.03 in},\hspace{-0.03 in}7^1\hspace{-0.03 in},\hspace{-0.03 in}8^8\hspace{-0.03 in},\hspace{-0.03 in}9^1\hspace{-0.03 in},...\hspace{-0.05 in}\right\rangle \:$ is super-linear but not $\omega \hspace{.02 in}(n)$.
Although such even-odd behavior could be handled by padding, one might instead
have extremely long streaks of super-polynomial values between low values.)

Improve this question
$\endgroup$
11
  • 2
    $\begingroup$ I think super-linear lower-bounds means there is a lowerbound in $\omega(n)$. $\endgroup$
    – Kaveh
    Sep 25, 2015 at 1:56
  • 4
    $\begingroup$ I don't think we call that a superlinear function. As far as I know what people mean by superlinear is $\omega(n)$ the same way that sublinear is $o(n)$. Do you have any reference for the use of superlinear in your sense? You sequence is infinitely often superlinear but it is not superlinear. $\endgroup$
    – Kaveh
    Sep 25, 2015 at 3:01
  • 3
    $\begingroup$ I believe the standard usage is that "superlinear circuit size" means that it does not have circuits of size $O(n)$, i.e. infinitely often. "Almost everywhere" lower bounds are much rarer and much harder to achieve. $\endgroup$
    – Joshua Grochow
    Sep 25, 2015 at 4:48
  • 2
    $\begingroup$ See Fortnow's blog post about the question of what's the right definition of the big omega notation. $\endgroup$
    – Robin Kothari
    Sep 25, 2015 at 14:14
  • 3
    $\begingroup$ @Kaveh: Sorry, I should have been more specific. I meant the statement that "problem X does not have linear size circuits" is generally equivalent to saying that "problem X has a super-linear circuit size lower bound", and I believe both of these mean (and should mean) what I said in my previous comments. The phrase "problem X has super-linear size circuits" seems strange to me, because "having such-and-such circuits" is an upper bound, but "super-linear" is a lower bound... $\endgroup$
    – Joshua Grochow
    Sep 26, 2015 at 0:38

2 Answers 2

Reset to default
9
$\begingroup$

$S^p_2$ and $PP$ are both known not to have $n^k$-circuits for any fixed k and there is no known containment between them. Details in my blog post.

Update: As Rickey Demer points out, these results do not necessarily give a language with a lower bound for all $n$ in $S_2^p$. I think the $\Delta^p_3$ is probably the best known. Since $PP$ has complete sets you might be able to get a all $n$ bound but I don't have a full proof.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ How do you go from "does not have n$^k$-size circuits" to an ​ $\omega(n)$ ​ circuit size lower bound? $\hspace{.84 in}$ See the top of this page for a sequence which has no polynomial upper bound but is not ​ $\omega(n)$ .) $\hspace{.58 in}$ $\endgroup$
    – user6973
    Mar 29, 2017 at 22:41
  • $\begingroup$ @EmilJeřábek : ​ ​ ​ How do you get that for all sufficiently large $n$ rather than just for infinitely many $n$? $\hspace{.08 in}$ (That would be needed to get "circuit size is $\omega(n)$" rather than "circuit size is not $O(n)$.) $\hspace{1.12 in}$ $\endgroup$
    – user6973
    Mar 29, 2017 at 22:51
  • $\begingroup$ @EmilJeřábek : ​ ​ ​ See my response at ​ meta.stackexchange.com/a/293100/232555 . ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user6973
    Mar 30, 2017 at 8:49
  • 2
    $\begingroup$ You're right, I was concentrating on the first part of the proof that's missing on the blog, and didn't realize there is a huge problem with the case distinction. So, anyway, there is a language in $\Delta^P_3$ that needs circuits of size $\ge n^k$ for all sufficiently large $n$. $\endgroup$
    – Emil Jeřábek
    Mar 30, 2017 at 9:39
  • 1
    $\begingroup$ Can get an almost-everywhere lower bound for $P^{PP[n^2]}$. For each $n$, let $S$ be the set of all circuits of size $n\log n$. For $i=1,\ldots,n^2$, call the oracle once to determine what the majority of circuits in $S$ answer on the $i$th input of length $n$, and throw out of $S$ all circuits that give this answer (this can be encoded as a polytime constraint on the next oracle call). Our hard function will output the opposite value on the $i$th input of length $n$.. End for. Now, given an a.e.-lb for $P^{PP[n^2]}$, can we lift it to $PP$? $\endgroup$
    – Ryan Williams
    Apr 5, 2017 at 6:40
2
$\begingroup$

Let dMCSP be the decisional version of the Minimum Circuit Size Problem,
and let "[1]" indicate "only 1 query".
The answer to my question seems to be ​ $\mathbf{P}^{\left(\mathbf{NP}^{\hspace{.032 in}\operatorname{dMCSP}[1]}\hspace{-0.03 in}\right)}$ , ​ which in fact
is such that for each positive integer k, it has a ​ $\omega \hspace{-0.02 in}\big(\hspace{-0.03 in}n^k\hspace{-0.03 in}\big)$ ​ lower bound:

Follow ​ the ending paragraph of page 7 ​ from this paper, with that paragraph's $k$ being one more than this argument's $k$, and additionally "observe that it is a" co_dMCSP "task to decide whether
a given truth table of length $\ell$ is hard", in the same sense as used in that page-7 paragraph.


The DNF circuits for an arbitrarily length-$\ell$ truth table have size at most ​ $\ell^{\hspace{.03 in}2} \cdot \operatorname{polylog}(\ell)$ ,
so dMCSP is in ​ $\mathbf{NP}$ . ​ ​ ​ Therefore ​ $\mathbf{P}^{\left(\mathbf{NP}^{\hspace{.032 in}\operatorname{dMCSP}[1]}\hspace{-0.03 in}\right)} \subseteq \mathbf{P}^{\left(\mathbf{NP}^{\hspace{.032 in}\operatorname{dMCSP}}\hspace{-0.03 in}\right)} \subseteq \mathbf{P}^{\left(\mathbf{NP}^{\hspace{.03 in}\mathbf{NP}}\hspace{-0.03 in}\right)} = \Delta^p_3$ .

I'm not aware of any proof that either of those $\subseteq$s are equalities, and this paper gives significant obstructions to the possibility of dMCSP being ​ $\mathbf{NP}$-hard ​ under randomized Turing reductions.
The equalities would follow from dMCSP being ​ $\mathbf{NP}$-hard ​ under strong non-deterministic (page 6) one-query reductions that take a polynomial-size advice string which is computable
by ​ $\mathbf{P}^{\left(\mathbf{NP}^{\hspace{.032 in}\operatorname{dMCSP}[1]}\hspace{-0.03 in}\right)}$ , ​ but in particular I'm not aware of any proof of such hardness.

Improve this answer
$\endgroup$

Your Answer

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