\documentclass{article}
\usepackage{epigraph, amsmath, amsthm, amssymb}

\title{P = PSPACE: incomplete notes towards a proof}

\author{Eric Purdy \\ Ketan Mulmuley \\ L\'{a}szl\'{o} Babai \\ Your name here}

\begin{document}

\maketitle
\epigraph{We are computer scientists. We do not lack in faith.}{Ketan Mulmuley}
\epigraph{It is like a finger pointing at the moon. It will never reach the moon. And yet, it points.}{Ketan Mulmuley}

Technically this is a proof that P $\ne$ NP, but it also shows why
that's a deeply irrelevant question to real life.

These are some brief notes that should allow anyone with mathematical
training of a sufficiently high level to complete the proof on their
own. The secret ingredient to the proof is Ketan Mulmuley's Geometric
Complexity Theory; it is so central to the proof that I have taken the
liberty of adding Dr. Mulmuley's name to this paper. The other secret
ingredient is the notion of Merlin-Arthur games, due to L\'{a}szl\'{o}
Babai. This is again so central that I have taken the liberty of
adding Dr. Babai's name to this paper.

\section{Proof outline}

We formulate an eight-player game with the following players on the following teams:
\begin{tabular}{|c|c|c|c|c|}
  \hline

  Team & Good & Evil & Sane & Insane \\
  
  \hline
  
  Unbounded Player & Merlin & Morgana Le Fay & God & Satan \\

  \hline
  
  Bounded Player & Arthur & Mordred & Jesus & Murphy's Demon \\
  
  \hline

\end{tabular}

Play proceeds as follows: first teams good and evil take turns
guessing certificates in the standard way for non-deterministic
computations. All certificates are guessed by either Merlin (for team
Good, existential quantifiers) or Morgana Le Fay (for team Evil,
universal quantifiers).

We then perform the computation, checking to make sure that the
computational device has not been corrupted by an infinitely powerful
adversary between steps. The only way to do this for certain is to
play against an infinitely powerful adversary and win. Thus, teams
Sane and Insane perform this part of the check. All moves must be made
by Jesus or Murphy's Demon, but they can seek advice from God and
Satan respectively. Team Sane wins if Good wins and Evil loses, or
vice versa. Team Insane wins if Good and Evil both think they won, or
if Good and Evil both think they lost.

Finally, we note that Dr. Mulmuley's Geometric Complexity Theory
allows one to devise certificates of impossibility that are checkable
in polynomial time by a deterministic computer. Thus, the unbounded
players can prove to the satsifaction of the bounded players that the
other team cannot possibly win on the next move.

Note that in classical models of computation, computation must be
local, i.e., the computational device can only pay attention to $O(1)$
things simultaneously. This is a stupid restriction, and allows Team
Insane to win in every situation. This is because Team Insane can
corrupt any part of the computation that is not currently being
attended to, so they can easily run circles around Team Sane.

\section{Finish it!}

You can come to me for advice if the above is not sufficiently
clear. I suspect it's not that clear, given how short it is.

\end{document}
