9

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.)

Community
  • 1
  • 2
    I think super-linear lower-bounds means there is a lowerbound in $\omega(n)$. – Kaveh Sep 25 '15 at 01:56
  • Look at the sequence I gave. $;$ –  Sep 25 '15 at 02:12
  • Let me see if I understand. For a problem whose minimal circuits have size $f(n)$ on inputs of size $n$, you say that problem has circuit size $\omega(n)$ if $\lim\inf f(n)/n = \infty$. (This is a different condition from the standard notion of having circuit complexity $\omega(n)$, which I believe is $\lim\sup f(n)/n = \infty$.) And your question is, "What is the 'smallest' complexity class containing a problem of circuit size $\omega(n)$?" Is that right? – usul Sep 25 '15 at 02:58
  • 4
    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. – Kaveh Sep 25 '15 at 03:01
  • @usul : $:$ Yes. $;;;;$ –  Sep 25 '15 at 03:04
  • 1
    @Kaveh : $;;;$ I don't; I just thought it came from the preorder given by $\hspace{1.67 in}$ $f \preceq g :$ if and only if $: f\in O(g) ;$. $;;;;;;;;$ –  Sep 25 '15 at 03:14
  • 3
    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. – Joshua Grochow Sep 25 '15 at 04:48
  • 2
    See Fortnow's blog post about the question of what's the right definition of the big omega notation. – Robin Kothari Sep 25 '15 at 14:14
  • @Josh, if that would be the case then "it has a superlinear size circuit" would mean "it does not have a linear size circuit" which would be quite strange. See also my comment below. – Kaveh Sep 25 '15 at 23:01
  • @Robin, see this. I know Lance promotes using lower bounds in the infinitely often sense. If it is not bounding point-wise it is not a bound. – Kaveh Sep 25 '15 at 23:06
  • 3
    @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... – Joshua Grochow Sep 26 '15 at 00:38

2 Answers2

9

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

Lance Fortnow
  • 8,681
  • 44
  • 59
  • 1
    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}$ –  Mar 29 '17 at 22:41
  • @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}$ –  Mar 29 '17 at 22:51
  • @EmilJeřábek : ​ ​ ​ See my response at ​ https://meta.stackexchange.com/a/293100/232555 . ​ ​ ​ ​ ​ ​ ​ ​ –  Mar 30 '17 at 08:49
  • 2
    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$. – Emil Jeřábek Mar 30 '17 at 09:39
  • @LanceFortnow : ​ Emil withdrew his initial response to me, so my comment $\hspace{1.7 in}$ right below your post remains unanswered. ​ ​ ​ ​ –  Apr 03 '17 at 01:27
  • 1
    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$? – Ryan Williams Apr 05 '17 at 06:40
2

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.