# Law of the Excluded Middle in complexity theory

A recent blog post by Lance Fortnow discusses non-constructive proofs, where "non-constructive" here means that the law of the excluded middle is used in a substantive way. That is, one takes some proposition $$P$$ whose truth is unknown, and splits the proof into two cases: (1) $$P$$ is true, and (2) $$P$$ is false. In both cases we deduce the desired theorem, but by totally different arguments. Fortnow gives an example from complexity theory:

In complexity, a well-known non-constructive theorem is by Kannan, showing that $$\Sigma_2^P$$ does not have $$n^2$$-size circuits.

1. SAT doesn't have $$n^2$$-size circuits. Since SAT is in $$\Sigma_2$$, we are done.
2. SAT has $$n^2$$-size circuits. Then by Karp–Lipton, $$\Sigma_4 = \Sigma_2$$ so L is in $$\Sigma_2$$ and we are done.

My question is, are there other proofs of results in complexity theory that are non-constructive in this sense?

Sometime in the past five years, I remember seeing such a paper, but unfortunately I can't remember anything else about it. I think it was a paper that had been recently published (though there's a chance it was an older paper that I had only just learned about). I also think the topic was circuit lower bounds, though I'm even less sure about that. Anyway, I'm interested in any examples, not just the one that I'm struggling to recall.

• What about results that use the existence of a finite obstruction set for minor-closed families? (Many algorithms parametrized by genus, for example, use this.) It's a bit more indirect than the example from Kannan's Thm, but I think still nonconstructive... Sep 11 at 20:12
• Sep 11 at 20:16
• @JoshuaGrochow Yes, that counts. I was thinking more of lower bounds than upper bounds, but I didn't say so explicitly in my question, so that sort of thing is fair game. Sep 11 at 20:31
• This has nothing to do with the question, it's just for the sake of clarity: the quoted proof from Fortnow's article is a bit puzzling because it mentions an undefined problem $\mathsf{L}$, which is not defined in the rest of the blog article either. Someone on the blog commented that $\mathsf{L}$ is a problem having no $n^2$-size circuits by diagonalization and which may be shown to be in $\Sigma_4$, as mentioned in this older blog article, from which that snippet was copied-and-pasted. Sep 12 at 14:58
• @DamianoMazza Thank you! I was just about to ask 'What is L?" Sep 12 at 15:33

There are several other non-constructive arguments that work along similar Karp-Lipton-esque lines, such as Santhanam's proof (STOC 2009) that $$PromiseMA$$ is not in $$SIZE(n^k)$$ for some $$k$$, and Kabanets-Impagliazzo-Volkovich's proof (CCC 2018) that $$ZPEXP^{MCSP}$$ is not in $$P/poly$$.
$$P$$ is not in $$P$$-uniform $$SIZE(n^k)$$ for every fixed $$k$$.
The proof is not constructive: it does not name any function in P that exhibits the lower bound. We don't even know a time upper bound on the hard $$P$$-function (otherwise, we could take some generic simulation language as the hard function).
I've tried off and on for some years to give a specific function satisfying the lower bound. The best I could do so far is with Cody Murray, where we showed that there is a function in time $$n^2$$ that isn't in $$LOGSPACE$$-uniform $$SIZE(n^{1+o(1)})$$. See https://drops.dagstuhl.de/opus/volltexte/2017/7542/