Complexity is a unique field because most of the important problems are unsolved. There is a giant web of implications of open problems, their barriers, and their relations.

I am talking about $\mathsf{P} \stackrel{?}{=} \mathsf{NP}, \mathsf{P} \stackrel{?}{=} \mathsf{PSPACE}$, and so on. I want to describe a way of thinking in complexity under these adversial conditions. This isn’t true for other fields. In cryptography, a field with foundation in complexity, you don’t have to think this way.

Every time a result or a theorem is shown, the thought process should be, “Okay, can this apply to the many open problems?” Here is one scenario where I have found that thinking this way can give some very deep intuition.

Consider Savitch’s theorem. For any $f$ is $\Omega(\log n)$, we have that $\mathsf{NSPACE}(f(n)) \subseteq \mathsf{DSPACE}((f(n)^2)$. Since polynomials are closed under complement, you should notice that immediately we get as a corollary that $\mathsf{NPSPACE} = \mathsf{PSPACE}$.

Here is where the intution can help us. Seeing the previous statement, the neurons in your brain should start firing. Just given this corollary, you can infer some things about how the proof of Savitch’s theorem has to work. Lets list out the thought process verbosely:

• The proof would work by a double set containment, and one of them is obvious.
• The other direction must involve some kind of “de-nondeterminisifying” technique. There is a way to somehow simulate a nondeterministic machine deterministically, with only quadratic overhead space cost.
• $\mathsf{P} \stackrel{?}{=} \mathsf{NP}$ is still an open problem
• If this technique could also apply to $\mathsf{P} \stackrel{?}{=} \mathsf{NP}$, then someone would have found a way to do this by now
• THEREFORE:
• The fact that $\mathsf{P} \stackrel{?}{=} \mathsf{NP}$ is remains open implies that the technique used to prove Savitch’s theorem does not have polynomial overhead time cost
• The technique used in Savitch’s theorem cannot apply to $\mathsf{P} \stackrel{?}{=} \mathsf{NP}$
• As polynomials are closed under composition, It should run in deterministic quasi-polynomial time, exponential time, or more.

And as it would turn out, we are correct. This chain of thought is loose, and not too formal but thats okay. Our intution here brought us some significant details of a proof to light without even seeing it. All we needed was the knowledge that an open problem is still open, and the statement of the theorem. We were only given those two pieces of information. Under the current research landscape, we can make some strong assumptions about what the proof has to look like.

This is just a small example, but this kind of thinking has helped me tremendously. Sometimes, I will see a result and think “Because of all the open problems, this can’t say anything too important. So it must have some structure like so and so.”

I think its still open problem if Savitch’s theorem is tight. Many space complexity theorems are interesting because they can use non-polynomial time techniques, like those used in undecidability and reducibility. Richard Lipton, on his blog, gives some history of Savitch’s theorem here