2026-09-16

2026-09-16 TOC scribe

$\newcommand{\BS}{\{0, 1\}}$ $\newcommand{\N}{\mathbb{N}}$ $\newcommand{\P}{\mathbf{P}}$ $\newcommand{\PSPACE}{\textbf{PSPACE}}$ $\newcommand{\NSPACE}{\textbf{NSPACE}}$ $\newcommand{\SPACE}{\textbf{SPACE}}$ $\newcommand{\PSC}{\textbf{PSPACE-complete}}$ $\newcommand{\L}{\textbf{L}}$ $\newcommand{\NL}{\textbf{NL}}$ $\newcommand{\coNL}{\textbf{coNL}}$ $\newcommand{\TQBF}{\textsf{TQBF}}$

QBF

Last class we saw that $\textsf{TQBF}\in \PSPACE\textbf{-complete}$

The general form of TQBF was

$Q_1x_1Q_2x_2\ldots Q_nx_n\varphi(x_1\ldots x_n)$

where $Q_n \in \{\exists, \forall\}$

we can convert this into a special format

$\exists x_1 \forall x_2 \exists x_3 \forall x_4 \ldots \exists \underline{x_{2n-1} \forall x_{2n}}\varphi(x_1\ldots \underline{x_{2n}})$

Notice we are using twice as many variables as the original format.

We say that this is as powerful as the above formula. We can encode any formula from $\TQBF$ in the above format by either copying them over if their indexes match or inject dummy variables.

This fixed format gives us the advantage of not having to encode the quantifiers. We can figure them out just by looking at the index.

Aside from that this format models a 2-player game.

Player 1 is playing $\exists$ and Player 2 is playing $\forall$

Player 1 has a “strategy” for all the moves made by player 2

The outcome is determined by the formula meaning if it is satisfied then we have a winning strategy for player regardless of player 2’s action.

Games and $\PSC$ness

Many games in the real world are $\in\PSC$ if we could reduce them down to a QBF. $2n$ would correspond to the game size. As they are in $\PSPACE$ this gives matches our intuition of their hardness. We have to optimize over quantifiers which is no easy task.

Savitch’s theorem

$\forall S(n): \N \rightarrow \N, S(n)\ge \log n$ that are space-constructible we have

$$\NSPACE (S(n)) \subseteq \SPACE(S(n))$$

PROOF: TODO

We just use the QBF conversion to 2n QBF and the proof is similar to the one we saw for TQBF $\in \PSC$

We reduce to $\NSPACE(S(n)^2)$ which can be shown to be equal to $\SPACE(S(n)^2)$

Corollary

$$\PSPACE = \NSPACE$$

This is rather surprising considering we have no idea about how to prove/disprove $P \overset{?}{=} NP$

Logarithmic space

$\L \overset{\text{def}}{=} \SPACE(\log n)$

$\NL \overset{\text{def}}{=} \NSPACE(\log n)$

$\L \overset{?}{\subseteq} NL \overset{?}{\subseteq} SPACE(\log^2n) = \L^2 \subseteq \P$

We don’t know if $\NL \subsetneq \P$

Something something $\log n$ -> $2^{\log n}$ = n

Why even care about $\SPACE$

Many games in real life is captured naturally through $\SPACE$. We also know that games are much harder than puzzles ($\mathbf{NP}$)

Complement classes

We’ve seen that all our definitions involve membership in a language. What about it’s complement? This is defined through complement classes.

If $S \subseteq \{f: \BS^\ast\rightarrow\BS\}$

Then $\mathbf{co}S \overset{\text{def}}{=} \{ \neg f(x) : f\in S \}$

$\mathbf{coP} = \P$

$\mathbf{coNP} \overset{?}{=} \mathbf{NP}$

Most people believe the following

We don’t know if there is a ladner theorem-esque problem that is in both $\mathbf{coNP}$ and $\mathbf{NP}$ but not in $\P$

$\mathsf{NotSAT} = \{\varphi : \forall \vec{x}, \varphi(\vec{x}) = 0\}\in \mathbf{coNP}$

$\mathsf{TAUTOLOGY} = \{\varphi : \forall \vec{x}, \varphi(\vec{x}) = 1\}= \neg \mathsf{NotSAT}$

Alternate definition of $\mathbf{coNP}$

$F\in\mathbf{coNP}$ iff $\exists\text{ TM } V,\text{ poly }p(n)\text{ s.t. }F(x) = 1\iff\forall w \in \BS^{p(n)} V(x, w) = 1$

We have a “short” witness of non-membership. Notice that this is very different. For a membership it is easy to understand what the witness looks like. For decision problem, we most often as have the answer as the witness. But for non-membership what would that look like? This is why most people believe they are different.

Even if you had oracle access to $\mathsf{SAT}$ you cannot solve $\mathsf{TAUTOLOGY}$. Think about that!

Some examples of the relationship between languages and their complements

$\L = \mathbf{coL}$

Question

$\NL \overset{?}{=} \mathbf{coNL}$

Yes. It is equal

More incredibly,

$$\mathbf{co}\NSPACE(S(n)) = \NSPACE(S(n)), \forall S(n)\ge \log n$$

Proof of $\NL = \mathbf{coNL}$

We define $\mathsf{PATH}(G, s, t) = \begin{cases}1 \iff \exists\text{ path from s to t}&\ 0\text{ otherwise}\end{cases}$

We say that $\mathsf{PATH}\in \NL$ and it is also $\NL\text{-complete}$

Meaning every problem in $\NL$ can be reduced to $\mathsf{PATH}$

Log-space reductions

Notice that we can’t really use our poly-* reductions as before. $\L\subsetneq \PSPACE$. The reduction could solve the problem itself. We cannot have the reduction be more powerful that the caller.

Hence we place a restriction saying that each output cell is write-once, not-readable. So the reduction spits out bit by bit but cannot go back and see what it had outputted.

$\text{TM }R = \begin{cases}\text{output: R/}&\\text{Work: R/W}&\\text{Output: W-once}\end{cases}$

Can $R$ output infinite bits? No. Since it’s work tape is logarithmic it cannot have configurations to output anything larger than polynomial

$\textsf{NotPATH}\in\mathbf{coNL}$ and is $\mathbf{coNL}\text{-complete}$

Theorem: if $\mathsf{NotPATH}\in\NL\implies \NL=\mathbf{coNL}$

I will repeat the same question about the witness. It is pretty clear what the witness would be for $\mathsf{PATH}$ which would be the path itself. But what about $\mathsf{NotPATH}$? How to concisely say that no path exists?

We construct a proof using recursion

$\mathsf{Cert}(v \in S_i)\text{ if s->v in }\le i\text{ steps}$