\documentclass[12pt]{article}
\usepackage[margin=1in]{geometry}
\PassOptionsToPackage{usenames,dvipsnames}{xcolor}
\usepackage{tcolorbox}
\usepackage{amssymb}
\tcbuselibrary{theorems}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage[T1]{fontenc}
\usepackage{pgf,tikz,pgfplots}
\usepackage{mathrsfs}
\usepackage[symbol]{footmisc}
\usepackage{tikz-cd}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\pmmp}{pmmp}
\DeclareMathOperator{\shmvp}{shmvp}
\theoremstyle{definition}
\newtheorem{myth}{Teorem\"{e}}
\newtheorem{myd}[myth]{Definition}
\newtheorem{myp}[myth]{Problem}
\newcommand{\ord}[2]{\text{ord}_{#1}(#2)}
\newcommand{\cho}[2]{{#1 \choose #2}}
\newcommand{\deff}[1]{\textbf{\textcolor{RubineRed}{#1}}}
\newcommand{\NP}{\text{NP}}
\newcommand{\NC}{\text{NC}}
\newcommand{\NL}{\text{NL}}
\newcommand{\coNL}{\text{co-NL}}
\newcommand{\EXPTIME}{\text{EXPTIME}}
\newcommand{\NEXPTIME}{\text{NEXPTIME}}
\newcommand{\PSPACE}{\text{PSPACE}}
\newcommand{\NPSPACE}{\text{NPSPACE}}
\newcommand{\EXPSPACE}{\text{EXPSPACE}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\charr}{\text{char}}
\newcommand{\tr}{\text{tr}}
\newcommand{\Hom}{\text{Hom}}
\newcommand{\Image}{\text{Im}}
\newcommand{\Gal}{\text{Gal}}
\newcommand{\Aut}{\text{Aut}}
\newcommand{\Der}{\text{Der}}
\newcommand{\modd}{\text{-mod}}
\newcommand{\tikzxmark}{%
\tikz[scale=0.23] {
    \draw[line width=0.7,line cap=round] (0,0) to [bend left=6] (1,1);
    \draw[line width=0.7,line cap=round] (0.2,0.95) to [bend right=3] (0.8,0.05);
}}
\newcommand\restr[2]{{% we make the whole thing an ordinary symbol
  \left.\kern-\nulldelimiterspace % automatically resize the bar with \right
  #1 % the function
  \littletaller % pretend it's a little taller at normal size
  \right|_{#2} % this is the delimiter
  }}

\newcommand{\littletaller}{\mathchoice{\vphantom{\big|}}{}{}{}}

%%%%%%% Problem Environment  %%%%%%%%%%%%%%%%%
\newtheoremstyle{problemstyle}  % <name>
        {10pt}                                               % <space above>
        {10pt}                                               % <space below>
        {\normalfont}                               % <body font>
        {}                                                  % <indent amount}
        {\normalfont\bfseries}                 % <theorem head font>
        {\normalfont\bfseries.}         % <punctuation after theorem head>
        {.5em}                                          % <space after theorem head>
        {}                                                  % <theorem head spec (can be left empty, meaning `normal')>
\theoremstyle{problemstyle}

\newtheorem{problem}{Problem}[section] % Comment out [section] to remove section number dependence

%%%%  Ushtrime Enviroment  %%%%%

\newtheorem{exercise}{Exercise} % Comment out [section] to remove section number dependence


%%%% Theorem Environment %%%%
\newtcbtheorem
  [no counter]% init options
  {theo}% name
  {Theorem}% title
  {%
    colback=BlueGreen!5,
    colframe=green!35!blue,
    fonttitle=\bfseries, before
skip=20pt,after skip=20pt 
  }% options
  {theo}% prefix

%%%% Proposition Environment %%%%
\newtcbtheorem
  [no counter]% init options
  {proposition}% name
  {Proposition}% title
  {%
    colback=RedOrange!5,
    colframe=RedOrange!85!Orange,
    fonttitle=\bfseries, before
skip=20pt,after skip=20pt 
  }% options
  {proposition}% prefix

%%%% Corollary Environment %%%%
\newtcbtheorem
  [no counter]% init options
  {corollary}% name
  {Corollary}% title
  {%
    colback=Plum!10,
    colframe=Plum!95!Black,
    fonttitle=\bfseries, before
skip=20pt plus 2pt,after skip=20pt plus 2pt
  }% options
  {corollary}% prefix
%%%% Remark Environment %%%%
\newtcbtheorem
  [no counter]% init options
  {remark}% name
  {Remark}% title
  {%
    colback=OrangeRed!10,
    colframe=OrangeRed!95!Black,
    fonttitle=\bfseries, before
skip=20pt plus 2pt,after skip=20pt plus 2pt
  }% options
  {remark}% prefix  
%%%% Lemma Environment %%%%
\newtcbtheorem
  [no counter]% init options
  {lemma}% name
  {\textcolor{white}{Lemma}}% title
  {%
    colback=Violet!10,
    colframe=Violet!95!White,
    fonttitle=\bfseries, before
skip=20pt plus 2pt,after skip=20pt plus 2pt
  }% options
  {lemma}% prefix  

%%%%%  SOLUTION ENVIRONMENT %%%%%
\newenvironment{solution}{\renewcommand{\proofname}{Solution}\begin{proof}}{\end{proof}}
%%%%
\setlength\parindent{0pt}
\begin{document}
\title{Computational Complexity Notes}
\author{Leart Ajvazaj}
\date{January 2024}
\maketitle
Notes from my Computational Complexity class at Cambridge with Tim Gowers. Any mistake is with very high certainty mine.

\section*{Computational Problems}
\subsection*{Lecture 1}
Example: Given a graph $G$ with $n$ vertices and $x,y\in V(G)$.
Problem: is there a path from $x$ to $y$?\\
A problem has variable input and output. If the output belongs to $\{0,1\}$ or $\{\text{no}, \text{yes}\}$ the problem is called a \deff{decision problem}.\\
Write $\{0,1\}^*$ for the set $\bigcup_{n=1}^\infty \{0,1\}^n$, then a decision problem can be encoded as a \deff{Boolean function}, that is, a function $f:\{0,1\}^*\to\{0,1\}$.\\
The set $\{x\in\{0,1\}^*: f(x)=1\}$ is called the \deff{language} defined by $f$.
\subsubsection*{Turing Machines}
A \deff{Turing machine} formalizes the notion of an algorithm. A \deff{$k$-tape Turing machine} consists of: A collection of $k$ tapes, where a tape is an infinite sequence of \deff{cells}.
There's also a finite set $A$ called the \deff{alphabet} and each cell contains an element of $A$.
There's also a \deff{head} which is in a \deff{state} (an element of a finite set $S$ of states) and in a \deff{position} in each type.
$S$ contains two special states $S_{init}$ and $S_{halt}$.
A \deff{state} is a function that takes as input an element of $A^k\times S$ and outputs an element of $A^k\times S\times \{L,N,R\}^k$.
\begin{center}
    \includegraphics[width=0.73\textwidth]{fig1.png}
\end{center}
If $s$ is this "transition function", then the machine rewrites according to the $A^k$ component of the image; changes state according to the $S$ component; shifts the tapes according to the $\{L,N,R\}^k$ component.
One tape is designated as the input tape and doesn't change.
Another is the output tape.
All tapes except for the input tape start full of zeros.\\
If the machine reaches state $S_{halt}$, it stops.
If the input is $x$ and output $y$, we say that the machine computed $y$, given $x$.\\
Variants: Can assume that $A=\{0,1\}$: that $k=1$ (with a different convention: divide the tape such that "tape 1" is the places $1\pmod k$, ... "tape k" is the places $0\pmod k$.
\subsubsection*{Some Complexity Classes}
The \deff{complexity class $P$} consists of all Boolean functions $f:\{0,1\}^*\to\{0,1\}$ such that there exists a Turing machine $T$ and polynomial $p$ such that for any $x$, $T$ computes $f(x)$ in at most $p(|x|)$ steps, where $|x|=n$ if $x\in\{0,1\}^n$.\\
Example: The problem st-CONN (input: directed graph $G$ and two vertices, output: $0$ or $1$) belongs to $P$.\\
Another example: input: $m,n\in\N$ and output $mn$.
\subsection*{Lecture 2}
\subsubsection*{NP - Nondeterministic Polynomial Time}
Example: input: a graph $G$ with $n$ vertices.
Output: $1$ if and only if $G$ contains a Hamilton cycle.\\
Loosely, a nondeterministic algorithm is one that doesn't fully specify what it does.
$H$ outputs $f(s)=1$ if and only if there's some sequence of choices that leads to $f(x)=1$.\\
More formally a \deff{nondeterministic Turing machine} is one that has not one but two transition functions.
At each step it applies one or the other.
We say that it computes $f$ if $f(x)=1$ if and only if there is some sequence of choices that leads to output $1$ when input is $x$.\\
\deff{NP} is the class of functions computable in polynomial time by a nondeterministic Touring machine.\\
Alternative definition: $f\in NP$ if there's a polynomial $p$ and a function $g\in P$ such that for every $x\in\{0,1\}^*$, $f(x)=1$ if and only if $\exists y\in\{0,1\}^{p(|x|)}$ such that $g(x,y)=1$.\\
To see that this is equivalent, observe that if $f$ satisfies the second definition, then we can write down $y$ non-deterministically and apply $g$.
In the other direction, $g$ encodes the choices made by the nondeterministic Turing machine (NDTM), so given $y$, the computation can be done deterministically.\\
Big open problem: Does $P=NP$?
\subsubsection*{co-NP}
\begin{center}
    $f\in$\deff{co-NP} $\iff \neg f$ or $1-f \in NP$.
\end{center}
Alternatively, $f\in\text{co-NP}$ if and only if there exists a polynomial $p$ and $g\in P$ such that for all $x\in\{0,1\}^*$ $f(x)=1$ if and only if $\forall y\in\{0,1\}^{p(|x|)}$: $g(x,y)=1$.
\subsubsection*{The Polynomial Hierarchy}
Define $\sum_0^P$ and $\prod_0^P$ to be $P$.
If $\sum_k^P$ and $\prod_k^P$ have been defined then $f\in \sum_{k+1}^P$ if and only if there exists a polynomial $p$ and $g\in \prod_k^P$ such that $f(x)=1$ if and only if $\exists y$ such that $g(x,y)=1$. $f\in \prod_{k+1}^P$ if and only if there exists a polynomial $p$ and $g\in \sum_k^P$ such that $f(x)=1$ if and only if for all $y$: $g(x,y)=1$. In both cases $y\in \{0,1\}^{p(|x|)}$.\\
Example: $f\in \sum_5^P$ if and only if $\exists h\in P$ such that $f(x)=1$ if and only if $\exists y_1: \forall y_2 \exists y_3: \forall y_4 \exists y_5$: $h(x,y_1,\dots,y_5)=1$.\\
We define the \deff{Polynomial Hierarchy} as $PH=\bigcup_{k=0}^\infty \sum_k^P\cup \prod_k^P$.
\begin{center}
    \includegraphics[width=0.3\textwidth]{fig7.png}
\end{center}

\begin{proposition}{}{}
    If P=NP, then P=HP.
\end{proposition}
\begin{proof}
    Note that if P=NP, then P=co-NP.
    If $f\in \sum_{k+1}^P$ then there exists $g\in \prod_k^P$ such that $f(x)=1$ if and only if $\exists y$: $g(x,y)=1$.
    By induction, $g\in P$ so $f\in$NP implies $f\in$P.
    The proof for $\prod_{k+1}^P$ is similar (or just look at the negation).
\end{proof}
Exercises on sheet: If NP=co-NP, then PH=NP=co-NP.
If $\sum_k^P=\sum_{k+1}^P$ or $\sum_k^P=\prod_k^P$ then PH=$\sum_k^P$.
\subsubsection*{PSPACE}
\deff{PSPACE} consists of functions that can be computed by a Turing machine that uses only a polynomial amount of tape.
\begin{proposition}{}{}
    NP$\subset$PSPACE.
\end{proposition}
\begin{proof}
    Here's a sketch of the proof.
    If $f(x)=1$ if and only if $\exists y$: $g(x,y)=1$ where $g\in P$ then to compute $f$ by a brute force search on $y$.
    All you need to remember is which $y$ you have got to (in a sensible order) and whether you have formed $y$ such that $g(x,y)=1$.
    You can clear the space needed to compute each $g(x,y)$.
\end{proof}
Exercise on sheet: PH$\subset$PSPACE. 
\subsubsection*{EXPTIME}
\deff{EXPTIME} is the class of functions that can be computed in time $\exp(O(n^k))$ for some $k$. 
\subsection*{Lecture 3}
\begin{proposition}{}{}
    PSPACE$\subset$EXPTIME.
\end{proposition}
\begin{proof}
    Given a Turing machine in the middle of a computation define its \deff{configuration} to be its state, its position on each tape, and the values in all the cells in the tapes.\\
    If $T$ uses only a polynomial amount of space $p(n)$ for input of size $n$, and has $k$ tapes, then the number of possible configurations is at most $|S|\cdot p(n)^k\cdot|A|^{kp(n)}$ where $A$ is the alphabet.
    So if the computation goes on for longer than this, the configuration repeats (by pigeonhole) so it's eventually periodic, so doesn't halt.
\end{proof}
\subsubsection*{NEXPTIME}
\[f\in \deff{\NEXPTIME} \iff \exists g\in \EXPTIME: f(x)=1 \iff \exists y: g(x,y)=1. \]
\subsubsection*{EXPSPACE}
$f$ is in \deff{EXPSPACE} if $f$ can be computed using at most $\exp(p(n))$ space for an input of size $n$.\\
To recap, so far we have
\[\text{P}\subset\NP\subset \PSPACE\subset \EXPTIME \subset \NEXPTIME \subset \EXPSPACE.\]
\subsubsection*{Circuit Complexity}
A \deff{circuit} is a directed acyclic graph (DAG) such that each vertex is labelled as an \deff{input}, an \deff{AND} gate, an \deff{OR} gate, or a \deff{NOT} gate.
An input is a vertex of in-degree $0$.
A NOT gate has an in-degree $1$.
All vertices of in-degree $>1$ are AND gates or OR gates.
Vertices of out-degree $0$ are outputs. 
\begin{center}
    \includegraphics[width=0.4\textwidth]{fig6.png}
\end{center}
If the vertex preceding a NOT gate has value $x$ then the vertex at the NOT gate has value $1-x$.\\
The value at the AND gate is the minimum of the values of its predecessors.\\
The value at the OR gate is the maximum of the values at its predecessors.\\
Using these roles we get a well-defined function from $\{0,1\}^I$ to $\{0,1\}^O$ where $I$ is the set of inputs and $O$ the set of outputs.\\
If every AND gate and OR gate has in-degree $\leq k$ then we say that the circuit is of \deff{fanin} $\leq k$. 
We often restrict to circuits of fanin $\leq2$.
\subsubsection*{Straight-Line Computations}
Let $f:\{0,1\}^n\to\{0,1\}$.
A \deff{straight-line computation} of $f$ is a sequence of functions $f_1,f_2,\dots,f_m$ ($m$ is the \deff{length} of the computation) such that $f_i(x)=x_i$, $1\leq i\leq n$ and for each $i>n$ either $f_i=f_{j_1}\wedge \dots\wedge f_{j_k}$ for some $j_1,\dots,j_k<i$ or $f_i=f_{j_1}\vee \dots\vee f_{j_k}$ for some $j_1,\dots,j_k<i$ or $f_i=1-f_j$ for some $j<i$, and $f_m=f$.\\
By considering a total order on the vertices of a DAG such that if $v_1\to v_2$  in the DAG then $v_1<v_2$ we see that the smallest circuit that computes $f$ is the smallest length of a straight-line computation that computes $f$.
\begin{lemma}{}{}
    Every function $f:\{0,1\}^n\to\{0,1\}$ can be computed by a circuit of size at most exponential in $n$.
\end{lemma}
\begin{proposition}{}{}
    Let $f$ be a function that can be computed by a Turing machine $T$ with $k$ tapes in time $t(n)$ for inputs of size $n$.
    Then there's a family of circuits $(C_n)$ such that $|C_n|=O(t(n)^{k+2})$ and $C_n$ computes $f$ for inputs of size $n$.
\end{proposition}
\begin{proof}
    Let $S=\{s_1,\dots,s_r\}$ be the set of states of $T$.
    (assume the alphabet is $\{0,1\}$). 
    Then we can encode the configuration of $T$ at time $t$ using variables $\sigma_1(t),\dots,\sigma_r(t), \pi_i^h(t)$ where $1\leq i\leq t(n)$ and $1\leq h\leq k$, $v_i^h(t)$ where $\sigma_i(t)=1$ if and only if $T$ is in state $s_i$ at time $t$.
    $\pi_i^h(t)=1$ if and only if the head is at position $i$ on tape $h$ at time $t$.
    $v_i^h(t)=$ value in cell $i$ of tape $h$ at time time $t$.\\
    Note that $\sigma_i(t)=1$ if and only if $\exists j\leq r, \; i_1,\dots,i_k$ such that $\sigma_j(t-1)=1$ and $\pi_{i_h}^h(t-1)=1$ for $h=1,\dots,k$ and $\tau(s_j,v_{i_1}^{1}(t-1),\dots,v_{i_k}^k(t-1))$ has state component equal to $s_i$.\\
    For any given $i_1,\dots, i_k$ we have a function of $k+1$ variables to evaluate which we can do with a circuit of bounded (in terms of $k$) size.
    Hence we can calculate $\sigma_i(t)$ from the previous configuration in time $O(t(n)^k)$.\\
    Similarly, we can compute each position variable $\prod_i^h(t)$ from the configuration at time $t-1$ with a circuit of size $O(t(n)^k)$.
    So we can compute the configuration at time $t$ from the configuration at time $t-1$ with a circuit of size $O(t(n)^{k+1})$, so the result follows.
\end{proof}
\subsection*{Lecture 4}
\subsubsection*{P/poly}
This complexity class has three equivalent definitions.
$f\in$\deff{P/poly} if one of the following holds:
\begin{itemize}
    \item[(1)] There is a family $(C_n)$ of polynomial-size circuits such that $C_n$ computes $f(x)$ when $|x|=n$. (So trivially $P\subset P/poly$)
    \item[(2)] There is a polynomial $p$ and a sequence $(y_n)$ with $|y_n|=p(n)$ and a function $g\in P$ such that $f(x)=1$ if and only if $g(x,y_{|x|})=1$.
    \item[(3)] There is a sequence $(T_n)$ of Turing machines and a polynomial $p$ such that $T_n$ has $\leq p(n)$ states and $T_n$ computes $f(x)$ when $|x|=n$. 
\end{itemize}
A sequence $(C_n)$ of circuits is \deff{P-uniform} if there is a polynomial-time algorithm that generates it (i.e. given input $1^n=(\underset{n-\text{times}}{\underbrace{1,\dots,1}})$, it outputs $C_n$).
\begin{proof}
$\empty$\\
    $(1)\Rightarrow(2)$: Let $y_n$ be an encoding of $C_n$ and let $g(x,y)=1$ if the circuit encoded by $y$ outputs $1$ with input $x$.\\
    $(2)\Rightarrow(1)$: Fix an input size $n$. Let $C_n'$ compute $g$ and let $C_n$ be $C_n'$ with the last $p(n)$ inputs restricted to $y_n$.\\
    $(2)\Rightarrow(3)$: Fix $n$. Let $T$ compute $g$ and let $T_n$ be a Turing machine that prints out $y_n$ and then uses $T$ to compute $g(x,y_n)$.\\
    $(3)\Rightarrow(2)$: Let $y_n$ be an encoding of $T_n$ and let $g(x,y)=1$ if the Turing machine encoded by $y$ outputs $1$ with input $x$.
\end{proof}
\subsubsection*{Search Problems \& Decision Problems}
Let $g$ be a Boolean function of two variables.
Then we get the decision problem "does there exists $y$ such that $g(x,y)=1?$" a corresponding \deff{search problem} is "if there exists $y$ such that $g(x,y)=1$, then find one."
A solution to a search problem is an algorithm that outputs $y$ such that $g(x,y)=1$ if it exists.
\begin{proposition}{}{}
    If $P=NP$ and $f\in NP$, $f(x)=1$if and only if there exists $y$ (with $|y|=p(|x|)$) such that $g(x,y)=1$ where $g\in P$. 
    Then there is a polynomial-time algorithm that computes $h:\{0,1\}^*\to\{0,1\}^*$ such that if $f(x)=1$ then $g(x,h(x))=1$.
\end{proposition}
The way you essentially prove this is by playing a game of 20 questions. You want to ask "is it possible for the $i$-th digit to be $1$?"
\begin{proof}
    For each $i$, let $g_i$ be the function that takes as input $x$ and $u_i$ where $|u_i|=i$ and outputs $1$ if and only if $\exists v$, $|v|=p(x)-i$ such that $g(x,u,v)=1$.\\
    Now run the following procedure: start by calculating $g_1(x,1)$ in polynomial time (sincere $P=NP$) and let $u_1=g_1(x,1)$.
    Note that if $\exists y$ such that $g(x,y)=1$ then $\exists v$ such that $g_1(x,u,v)=1$.
    Now let $u_2=g_2(x,u_1)$, $u_3=g_3(x,u_2)$ and so on.
    At the end we obtain $u=(u_1,\dots,u_{p(|x|)})$ such that $g(x,y)=1$.
\end{proof}
\begin{lemma}{}{}
    If $NP\subset P/poly$ then for $f$as above, there is a polynomial-sized family of circuits $(C_n)$ such that if $|x|=n$ then $C_n$ with input $x$ computes $y$ such that $g(x,y)=1$.
\end{lemma}
\begin{proof}
    For each $i$ since $NP\subset P/poly$ there is a polynomial-sized circuit $C_i'$ that computes $g_i$.
    Now put together the circuits $C_1',\dots,C_{p(n)}'$ as follows:
    \begin{center}
        $C_1'$ takes inputs $x_1,\dots,x_n,1$ and outputs $u_1$.\\
        $C_2'$ takes inputs $x_1,\dots,x_n,u_1,1$ and outputs $u_2$.\\
        Continue all the way to $C_{p(n)}'$
    \end{center}
    Then the output if there exists $y$ such that $g(x,y)=1$ will be such a $y$
\end{proof}
\begin{theo}{The Karp-Lipton Theorem}{}
    If $NP\subset P/poly$ then $\sum_2^P=\prod_2^P$ (and therefore $PH=\sum_2^P=\prod_2^P$)
\end{theo}
\subsection*{Lecture 5}
\begin{proof}
    Let $f\in \prod_2^P$ and let $h\in P$ be such that $f(x)=1 \iff \forall \; y \;\exists\; z:\;h(x,y,z)=1$ (where $y$ and $z$ are of appropriate polynomial size depending on $|x|$).
    Define $g(x,y)=1\iff \exists z:\; h(x,y,z)=1$.
    Therefore $g\in NP$, so by our hypothesis and the previous lemma there exists a circuit family $(C_n)$ of polynomial size such that for every $x$, if $|x|=n$ and $g(x,y)=1$, then $h(x,y,C_n(x,y))=1$ ($C_n(x,y)$=output of $C_n$ with input $x,y$).
    So $f(x)=1$ \textcolor{cyan}{implies} that there exists $C_n$ such that for all y we have $h(x,y,C_n(x,y))=1$.
    Checking whether $h(x,y,C_n(x,y))=1$ can be done in polynomial time.
    If $f(x)=0$ then $\exists y:\;\forall z:\; h(x,y,z)=0$, so the the \textcolor{cyan}{implies} is actually an $\iff$.
    Hence $f\in \prod_2^P$.
    By doing the same for $1-f$ we get the reverse inclusion.
\end{proof}
\begin{lemma}{}{}
    For every $k$ there's a boolean function $f$ that can be computed by a circuit family of size $n^{k+1}$ but not by a circuit family of size $n^k$.
\end{lemma}
\begin{proof}
    Exercise Sheet.
\end{proof}
\begin{theo}{}{}
    For every $k$ there is a boolean function $f\in\prod_4^P$ that cannot be computed by a family of circuits of size $n^k$.
\end{theo}
\begin{proof}
    For $n$ sufficiently large, the lemma gives us $f_n:\{0,1\}^n\to\{0,1\}$ that can be computed by a circuit of size $n^{k+1}$ but not by a circuit of size $n^k$.
    Choose a sensible ordering $(\prec)$ on circuits of size $\leq n^{k+1}$.
    Let $f_n(x)$ (if $|x|=n$) be $C_n(x)$ where $C_n$ is the first circuit (in this ordering) such that $|C_n|\leq n^{k+1}$ and no circuit of size $\leq n^k$ computes the same $f_n$ as $C_n$.
    Then let $f=(f_n)_{n=1}^\infty$ (if $n<n_0$, $f_n$ can be arbitrary).\\
    Then if $|x|=n$, we have that $f(x)=1$ if and only if there exists $C_n$ such that $|C_n|\leq n^{k+1}$ and for all circuits $D$ with $|D|\leq n^k$ $\exists y$ such that $C_n(y)\neq D(y)$ and for all $E\prec C_n$ there exists $F$ such that $|F|\leq n^k$ so that for all $z$, $E(z)=F(z)$ and $C_n(x)=1$.
    The $\exists\forall\exists\forall$ shows that $f\in\sum_4^P$.
\end{proof}
\begin{corollary}{}{}
    In fact, for every $k$ there is a function $f\in \sum_2^P\cap \prod_2^P$ that cannot be computed by a circuit family of size $n^k$.
\end{corollary}
\begin{proof}
    By Karp-Lipton \underline{if} $NP\subset P/poly$ then $PH\subset \sum_2^P\cap\prod_2^P$ so the function just defined does the job.
    If $NP\not\subset P/poly$ then we're done as we get the stronger result that there is $f\in \sum_1^P$ (=NP) that cannot be computed by any circuit family of polynomial size.
\end{proof}
\subsubsection*{L}
Roughly \deff{L} is functions that can be computed with a logarithmic amount of memory.
More formally, $f\in L$ if there is a Turing machine that computes $f$ with a read-only input tape that contains the input and cannot be modified, and a work tape of size $O(\log n)$ for inputs of size $n$. (if you want several outputs, you have a write-only output tape (i.e. can't read it))
\subsubsection*{NL}
\deff{NL} is like $L$ except that the Turing machine is nondeterministic.
We can also give a certificate definition of NL but one has to be careful.\\
We say that $f\in NL$ if there is a Turing machine with a read-only input tape, work tape of size $O(\log n)$ and a read-once certificate tape, on which the head can only ever stay still or move to the right, such that $f(x)=1\iff\exists y$ ($|y|\leq p(|x|)$) that can be put in the certificate tape such that the Turing machine outputs $1$.
\begin{proposition}{}{}
    \[NL\subset P\]
\end{proposition}
\subsection*{Lecture 6}
We prove the fact that $NL\subset P$.
\begin{proof}
    Let $f\in NL$, let $T$ be a non-deterministic Turing machine that computes $f$ in log space.
    Let $G$ be the \deff{configuration graph} of $T$.
    That is, the directed graph whose vertices are the configurations of $T$ and $C$ is joined to $C'$ if and only if it is possible for $T$ to go from $C$ to $C'$ in one step.
    Then $f(x)=1$ if and only if there is a directed path in $G$ from the initial configuration to $1$ such that $T$ has halted with output $1$.\\
    Since $T$ uses $O(\log n)$ space, the number of vertices of $G$ is polynomial in $n$.
    But \deff{reachability}, the problem of determining whether there is a directed path from a vertex $x$ to a subset $S$ of vertices in a directed graph is easily seen to be in $P$.
\end{proof}
\subsubsection*{Low-depth Computation}
The class \deff{$NC^i$} ($i\in\N_0$) consists of all functions that can be computed by a family of circuits of polynomial size and fanin $\leq2$ and depth $O((\log n)^i)$ where the \deff{depth} of a circuit is the length of the longest directed path in the associated DAG.\\
\deff{$AC^i$} is like $NC^i$ except that unbounded fanin is allowed.
We define $NC=\bigcup_{i=0}^\infty NC^i$ and $AC=\bigcup_{i=0}^\infty AC^i$.
It's easy to see that $NC=AC$ since $AC^i\subset NC^{i+1}$.
It's usual to impose a uniformity condition on $NC^i$.
The favored condition is log space uniformity. i.e. $f\in u-NC^i$ if the circuits can be generated in log space.\\
Major open problem: Is $P\subset NC$? In fact, it is not known whether $PH\subset NC^1$.
\subsubsection*{Randomized Computations}
A function $f$ is in \deff{RP} (randomized polynomial time) if there is a polynomial $p$ and a function $g\in P$ such that if $|x|=n$ and $m=p(n)$ then \[\mathbb{P}_{y\in\{0,1\}^m}[g(x,y)=1]\begin{cases}
    =0\text{ if }f(x)=0\\
    \geq\frac{1}{2}\text{ if }f(x)=1
\end{cases}\]
Note that if we run the computation on independent strings $y_1,\dots,y_k$ then $\mathbb{P}[\exists i: g(x,y_i)=1]\begin{cases}
    =0\text{ if }f(x)=0\\
    \geq1-2^{-k}\text{ if }f(x)=1
\end{cases}$
So we can make the error probability very small without much cost.\\
$f\in\deff{co-RP}$ if and only if $1-f\in RP$.\\
\deff{ZPP} (zero-error probabilistic polynomial time) $=RP\cap co-RP$.\\
$f\in\deff{BPP}$ (bounded-error probabilistic polynomial time) if there exists $g$ as above such that $\mathbb{P}_{y\in\{0,1\}^m}[g(x,y)=f(x)]\geq\dfrac{2}{3}$.\\
Again, we can shrink the error probability.
To do so, pick some $k$ and calculate $g(x,y_1),\dots,g(x,y_k)$ ($y_1,\dots,y_k$ independent) and take the majority.
The probability of getting the wrong answer is at most $e^{-k/48}$ by Chernoff estimates for the sum of independent Bernoulli random variables.
\begin{corollary}{}{}
    \[BPP\subset P/poly\]
\end{corollary}
\begin{proof}
    if $k\geq 48N$, then the probability that the majority of $g(x,y_i)$ is wrong is $<2^{-n}$.
    Therefore there exists $y_1,\dots,y_k$ such that for every $x$ the majority vote is correct.
    This $y_1,\dots,y_k$ serves as an advice string together with the function that computes the majority vote.
\end{proof}
\subsection*{Lecture 7}
\begin{theo}{Sipser-Lautemann}{}
    \[BPP\subset \sum_2^P\cap\prod_2^P.\]
\end{theo}
\begin{proof}
    If $f\in BPP$ then there exists a polynomial $p$ and $g\in P$ such that if $|x|=n$, then $\underset{y\in\{0,1\}^{p(n)}}{\mathbb{P}}[g(x,y)=f(x)]\geq1-2^{-n}$ (by the accuracy boosting argument).
    For each $x$, let $A_x\subset\{0,1\}^{p(n)}$ be $\{y:g(x,y)=1\}$.
    Then if $f(x)=1$, $A_x$ has density $\geq1-2^{-n}$ and if $f(x)=0$, then $A_x$ has density $\leq2^{-n}$.\\
    Suppose that $f(x)=1$ and let $y_1,\dots,y_r$ be chosen independently and uniformly from $\{0,1\}^{p(n)}$.
    For each $y$, $\mathbb{P}\left[y\not\in\bigcup_{i=1}^r A_x\oplus y_i\right]\leq 2^{-rn}$ where $\oplus$ is pointwise mod $2$ addition.\\
    So if we choose $r>\dfrac{p(n)}{n}$ this probability is less than $2^{-n}$, so $f(x)=1\Rightarrow\exists y_1,\dots,y_r$ such that $\bigcup_{i=1}^r A_x\oplus y_i=\{0,1\}^{p(n)}$.\\
    Equivalently, $f(x)=1\Rightarrow \exists y_1,\dots,y_r\;\forall y\in\{0,1\}^{p(n)} \;\overset{\text{in }P}{\overbrace{\exists i:\;g(x,y\oplus y_i)=1}}$.
    But if $f(x)=0\Rightarrow A_x$ has density $\leq2^{-n}$ and $r$ is polynomial in $n$, so (for sufficiently large $n$) it's not possible that $\bigcup_{i=1}^r A_x\oplus y_i=\{0,1\}^{p(n)}$ so the $\Rightarrow$ is a $\iff$ and therefore $f\in \sum_2^P$.
    By symmetry of BPP (i.e. $f\in BPP\iff1-f\in BPP$), $f\in \prod_2^P$.
\end{proof}
Major open problem: Does $BPP=P$?
\subsubsection*{\# P}
\deff{\#P} is a class for \deff{counting problems}. A function $f:\{0,1\}^*\to\N_0$ belongs to $\#P$ if there exists a polynomial $p$ and $g\in P$ such that for every $x\in\{0,1\}^*$, $f(x)=|\{y\in\{0,1\}^{(|x|)}: g(x,y)=1\}|$.
Note that if we can count solutions, then we can detect whether solutions exist, so $\#P$ is harder than $NP$.\\
\textit{Example:} Input a graph $G$. Output the number of Hamilton cycles in $G$.\\
\textit{Important Example:} Input a bipartite graph with vertex sets of the same size. Output the number of perfect matchings.\\
If $G$ is such a graph with two copies of $[n]$ as its vertex sets and if $A_{ij}=\begin{cases}
    1\;\;\; ij\in E(G)\\
    0\;\;\;\text{otherwise}
\end{cases}$
then the number of perfect matchings is $\displaystyle\sum_{\sigma\in S_n}\prod_{i=1}^n A_{i\sigma(i)}$.
This is called the \deff{permanent} of the $n\times n$ matrix $A$.
\subsubsection*{Algebraic Complexity}
Algebraic complexity is about building up multivariable polynomial using $+$ and $\times$.\\
An \deff{arithmetic circuit} is a DAG where each vertex is either an input, a $+$ gate or a $\times$ gate.
The inputs are constants from some given field $\F$, and variable $x_1,\dots,x_n$.
As with Boolean circuits we can talk instead about straight-line computations.\\
The \deff{degree} of a circuit is defined inductively.
The degree of an input vertex is $0$ if it's a constant and $1$ if it is a variable.
The degree at a $+$ gate is the maximum of degrees of its inputs. The degree at a $\times$ gate is the sum of the degrees of its inputs.
\subsubsection*{VP}
$\deff{VP}$ is the class of families of polynomials such that $p_n$ can be computed by an arithmetic circuit of polynomial size and polynomial degree.\\
Example: The determinant (of a matrix $(x_{ij})_{i,j=1}^n$) is in $VP$. (proof later)
\subsubsection*{VNP} 
A polynomial family $(f_n)$ is in \deff{VNP} if there is a polynomial $p$ and a polynomial family $(g_n)\in VP$ such that $f_n(x)=\displaystyle\sum_{y=(y_1,\dots,y_n)\in\{0,1\}^m}g_n(x,y)$ where $m=p(\#\text{variables in }x)$.
\subsection*{Lecture 8}
\textit{Example:} a permanent belongs to VNP.
\begin{proof}
    We must find a suitable way of representing the polynomial $\sum_{\pi\in S_n}\prod_{i=1}^n x_{i\pi(i)}$.
    For each $i$, let $r_i(y)=\sum_{j=1}^n y_{ij}\pi_{j'\neq j}(y_{ij}-y_{ij'})$ and note that $r_i(y)=1\iff$ there's exactly one $j$ such that $y_{ij}=1$. Let $r(y)=\prod_{i=1}^n r_i(y)$.
    Similarly define a polynomial $c(y)$ that takes the value $1$ iff $y$ has exactly one $1$ in each column.
    Then \[\sum_{y\in\{0,1\}^{[n]^2}}\prod_{i=1}^n\left(\sum_{j=1}^n x_{ij}y_{ij}\right)r(y)c(y)=per(x)\] and the above formula gives a polynomial size and polynomial degree arithmetic circuit.
\end{proof}
\section*{2. Completeness}
\subsection*{Lecture 8}
For many complexity classes there are problems in the classes that can be shoown to be as least as hard as any other problem in the class.
\subsubsection*{NP-Completeness}
Let $f,g$ be Boolean functions.
A function $h:\{0,1\}^*\to\{0,1\}^*$ is a \deff{polynomial-time reduction} from $g$ to $f$ if $h$ can be computed in polynomial time and $g=f\circ h$.
If $f\in P$ and $g$ be polynomial-time reduced to $f$, then $g\in P$.\\
We sometimes write $g\prec_Pf$.
Note that the relation $\prec_P$ is transitive.\\
$f$ is said to be \deff{NP-hard} if $g\prec_Pf$ for every $g\in NP$.
$f$ is \deff{NP-complete} if $f$ is NP-hard and $f\in NP$.\\
\textit{Example 1 (boring):} The input is a Turing machine $T$, some $x\in\{0,1\}^*$ and two unary sequences $1^m$ and $1^t$.
Then $\phi(T,x,1^m,1^t)=1$ if and only if there exists $y$ with $|y|=m$ such that $T$ halts on input $(x,y)$ in time $\leq t$ and outputs $1$.\\
Clearly $\phi\in NP$.
If $f\in NP$ and $p,q$ are polynomials and $g\in P$ such that $f(x)=1\iff\exists y\in\{0,1\}^{p(|x|)}$ such that $g(x,y)=1$ then let $T,q$ be such that $T$ computes $g(x,y)$ in time $\leq q(|x|)$.
Then $f(x)=1\iff\phi(T,x,1^{p(|x|)},1^{q(|x|)})=1$. Call that problem \deff{TSAT}.\\
\textit{Example 2 (CIRCUITSAT):} Here the input is a circuit $C$ with $n+m$ inputs and some $x\in\{0,1\}^n$.
The output is $1$ if and only if $\exists y\in\{0,1\}^n$ such that $C(x,y)$.\\
We can reduce TSAT to CIRCUITSAT. Given an instance $(T,x,1^m,1^t)$ of TSAT, build a circuit $C_T$ that emulates $T$ for $t$ steps with inputs of size $|x|+m$.
Then $\phi(T,x,1^m,1^t)=1\iff\exists y$ such that $C_T(x,y)=1$, completing the reduction.\\
For the next example we need some definitions.
A \deff{variable} is a symbol $x$ that stands for an element of $\{0,1\}$. A \deff{literal} is either $x$ or $\neg x$ for some variable $x$. A \deff{clause} is an expression of the form $u_1\vee u_2\vee\dots\vee u_k$ where $u_1,\dots,u_k$ are literals. A \deff{formula} is a conjunction of clauses. Eg $x_1\wedge(x_2\vee\neg x_3)\wedge(x_1\vee x_3)$. A formula $\phi$ is \deff{satisfiable } if it is possible to choose variables such that $\phi$ evaluates to $1$.\\
\textit{Example 3:} \deff{SAT} takes as input a formula and outputs $1$ if and only if it is satisfiable.\\
\deff{3SAT} is the special case where each clause has size $3$.\\
\begin{proof}
We shall reduce CIRCUITSAT to 3SAT.
First, let $v_1,\dots,v_m$ be some straight-line computation.\\
Assume fanin$\leq2$. For each $v_i$ we take a variable, which we shall also call $v_i$.
If $v_i=\neg v_j$ for some $j<i$, put in clauses $(\neg v_i)\vee(\neg v_j)$ and $v_i\vee v_j$ (we're doing $P\Rightarrow Q\iff P\vee \neg Q$). 
If $v_i=v_j\wedge v_k$ for some $j,k<i$, put in $\neg v_i\vee v_j, \neg v_i\vee v_k, \neg v_j\vee\neg v_k\vee v_i$.
If $v_i= v_j\vee v_k$ for some $j,k<i$, put in $\neg v_j\vee v_i, \neg v_k\vee v_i, \neg v_i\vee v_j\vee v_k$.\\
So far, if $v_1,\dots, v_m$ satisfy the formula then they must take values corresponding to the straight-line computation.
Now add the clause $v_m$ to force the output to be $1$.
Finally, given $C,x$, set the inputs corresponding to $x$ to be those values and simplify the formula to some $\phi_x$ which is satisfiable if and only if $\exists y$ such that $C(x,y)=1$.
\end{proof}
\subsection*{Lecture 9}
VERTEX COVER is the problem where the input is a graph $G$ and a positive integer $m$ and the output is $1$ if and only if there is a subset $A\subset V(G)$, $|A|=m$ such that every edge has a vertex in $A$.\\
To see that this is NP-complete we shall reduce 3SAT to it.
This we do with the help of "gadgets".
Let $\phi$ be a formula in $x_1,\dots,x_n$ of 3SAT (For convenience suppose that all clauses have size exactly $3$). 
For each $x_i$, build a "variable gadget" 
\begin{center}
    \includegraphics[width=0.3\textwidth]{fig2.png}
\end{center}
which is an edge with vertices labelled $x_i$ and $\neg x_i$.
For each clause $u_i\vee u_j\vee u_k$ we build a "clause gadget" as follows:
\begin{center}
    \includegraphics[width=0.4\textwidth]{fig3.png}
\end{center}
i.e. take a triangle and connect the three vertices to the vertices labelled $u_i,u_j,u_k$.\\
Observe that every vertex cover of the resulting graph has size at least $n+2m$, where $m$ is the number of clauses.\\
Claim that there is a vertex cover of size $n+2m$ if and only if $\phi$ is satisfiable.\\
\textit{proof of claim:} If $\phi$ is satisfiable, let $u_1,\dots, u_n$ be a satisfying assignment and pick $u_i$ from the $i$-th variable gadget and then for any clause gadget we have at least one of the outer edges covered, so can cover the rest with $2$ vertices.\\
If $\phi$ is not satisfiable, then for any choice of $u_1,\dots,u_n$ there will be some clause gadget with no outer edge covered so we'll need all three inner vertices.\qed
\begin{theo}{(Ladner)}{}
    If $P\neq NP$, then there is a problem in $NP$ that is neither in $P$ nor $NP$-complete.
\end{theo}
\begin{proof}
    Let $f:\N\to\N$ be a function to be defined.
    Then let $g:\{0,1\}^*\to\{0,1\}$ be defined as follows: If $u\in\{0,1\}^*$ has the form $x01^{f(|x|)}$ and $x$ encodes a satisfiable formula (in some sensible way), then $g(u)=1$.
    Otherwise $g(u)=0$.\\
    We shall define functions $i:\N\to\N$ and $f:\N\to\N$ recursively as follows.
    Enumerate all Turing machines as $T_1,T_2,\dots$ in such a way that each Turing machine occurs infinitely often.
    Also constrain $T_i$ to halt within $in^i$ steps.
    Observe that if $T$ is any Turing machine that halts in polynomial time, then it agrees with some $T_i$.\\
    If we have defined $i(1),\dots,i(n-1),f(1),\dots,f(n-1)$ then we set $i(n)$ to be $i(n-1)$ if $T_{i(n-1)}$ agrees with $g$ on all inputs of size $\leq \log n$ and $i(n-1)+1$ otherwise. $f(n)=n^{i(n)}i(n)$.
    Note that this isn't a circular definition as we have enough values of $f$ to compute $g$ on inputs of size $\leq n$.
    Note also that $f$ is polynomial-time in $n$ computable since we can do a brute-force search.\\
    Claim 1: $g\not\in P$.\\
    \textit{proof of claim 1:} If $g\in P$, then $g$ is computed by some $T_i$.
    But then $i(n)$ never goes above $i$.
    So $f(n)\leq in^i$ for all $n$ but then the amount of padding is polynomial in $|x|$, so if we can compute $g$ in polynomial time then $SAT\in P$ contradicting that $P\neq NP$.\\
    Claim 2: $g$ is not $NP$-complete.\\
    \textit{proof of claim 2:} If $g$ is NP-complete then we have a polynomial time reduction of SAT to $g$.
    If the reduction is in time $kn^k$, then the reduction is to an instance $u$ of $g$ of size at most $kn^k$.
    But for $n$ sufficiently large, $i(n)n^{i(n)}>kn^k$ which implies that the "x" part of $u$ has size less than $n$.
    So in polynomial time we reduce an instance of SAT to a smaller instance of SAT, so $SAT\in P$, but $P\neq NP$. $\rightarrow\leftarrow$.
\end{proof}
\subsubsection*{Completeness in Space Classes}
Let $s:\N\to\N$ then $DSPACE(s(n))$ is the class of functions computable by a Turing machine in space $O(s(n))$ and $NSPACE(s(n))$ is the class of functions computable by a non-deterministic Turing machine in space $O(s(n))$.
\begin{theo}{(Savitch)}{}
    If $s(n)$ grows at least as fast as $\log n$then $NSPACE(s(n))\subset DSPACE(s(n)^2)$.
\end{theo}
\begin{proof}
    Let $f\in NSPACE(s(n))$ and let $T$ be a NDTM that computes $f$ in space $s(n)$, and for any $x$ let $G_x$ be the configuration graph of $T$ with input $x$.
    Note that $|V(G)|=2^{O(s(n))}$ (since $s(n)\geq c\log n$).
    Then $f(x)=1\iff $ there is a path in $G_x$ from the initial configuration to the halt with output $1$ vertex
\subsection*{Lecture 10}
Let $\sigma(k)$ be the amount of space needed to determine whether there is a path of length $\leq2^k$ between two vertices of the configuration graph and let $g_k(u,v)=1$ if such a path exists from $u$ to $v$.\\
Then $g_k(u,v)=1\iff\exists w$ such that $g_{k-1}(u,w)=1$ and $g_{k-1}(w,v)=1$.
Therefore, $\sigma(k)\leq O(s(n))+\sigma(k-1)+1$ (reuse space!)\\
Also $\sigma(0)=O(s(n))$, so $\sigma(k)=O(k s(n))$.
Choose $k=O(s(n))$ such that $2^k>|V(G_x)|$ and we get the bound stated.
\end{proof}
\subsubsection*{A PSPACE-complete problem}
A \deff{quantified Boolean formula} (QBF) is a statement of the form \[Q_1x_1,Q_2x_2\dots Q_nx_n \phi(x_1,\dots,x_n)\]
where $\phi$ is built out of $x_1,\dots,x_n$ using $\neg,\vee,\wedge$ and each $Q_i$ is $\exists$ or $\forall$.\\
TQBF is the problem of determining whether a QBF is true.
\begin{theo}{}{}
    TQBF is PSPACE-complete.
\end{theo}
\begin{proof}
    First, let's show that TQBF is in PSPACE.
    Let $S(n,m)$ be the amount of space needed to solve TQBF for formulas of size $m$ with $n$ variables, where constants are allowed.\\
    Let P be the QBF $Q_1x_1\dots Q_nx_n\phi(x_1,\dots,x_n)$ where $\phi$ has size $m$.
    Then if $Q_1=\forall$ we get that $P$ is true if and only if $P|_{x_1=0}$ and $P|_{x_1=1}$ is true.\\
    The space needed to determine whether this is the case is at most $S(n-1,m)+1+O(m)$. Also $S(0,m)=O(m)$. Similarly, if $Q_1=\exists$. So $S(n,m)=O(nm)$.\\
    Now let $f\in PSPACE$. We want a polynomial-time reduction of $f$ to TQBF.
    Let $x\in\{0,1\}^*$, let $T$ be a Turing machine that computes $f$ in polynomial space, and let $G$ be the configuration graph of $T$ with input $x$.
    Then $f(x)=1$ if and only if there's a path in $G$ from $v_{init}$ to $V_{accept}$. Observe that $|V(G)|=2^{O(p(n))}$ for some polynomial $p$.\\
    For any $k,u,v$ let $Q(k,u,v)$ be the statement that there is a path in $G$ of length $\leq2^{k}$ from $u$ to $v$.
    Let $S(k)$ be the maximum size of a QBF that expresses $Q(k,u,v)$. Then 
    \begin{equation*}
        \begin{split}
            Q(k,u,v)&\iff\exists w: Q(k-1,u,w)\wedge Q(k-1,w,v)\\
            &\iff \exists w\;\forall y,z\; ((y=u\wedge z=w)\vee(y=w\wedge z=v))\Rightarrow Q(k-1,y,z).
        \end{split}
    \end{equation*}
    It follows that $S(k)\leq O(p(n))+S(k-1)$. Picking $k$ such that $2^k\geq|V(G)|$ we get $S(k)=O(p(n)^2)+S(0)$.\\
    But $Q(0,u,v)=1\iff u=v$ or $uv\in E(G)$.
    But we can find in polynomial time a formula of size polynomial in $n$ that determines whether one configuration is the successor of another - see proof of $P\subset P/poly$.
\end{proof}
\subsubsection{NL-Completeness}
A Boolean function $f:\{0,1\}^*\to\{0,1\}^*$ is \deff{implicitly log space computable} if for every $x$ and every $i$ the functions $1_{\{i\leq|f(x)|\}}$ and $f(x)_i$ are in $L$ (the latter only if $i\leq|f(x)|$).
\begin{lemma}{}{}
    If $f$ and $g$ are implicitly log space computable, then so is $g\circ f$.
\end{lemma}
\subsection*{Lecture 11}
Write ILC for implicitly logspace computable.
\begin{lemma}{}{}
    If $f$ and $g$ are ILC, then so is $g\circ f$.
\end{lemma}
\begin{proof}
    Look at recording 22/02/2024
\end{proof}
\textbf{Definition:} Let $f,g:\{0,1\}^*\to\{0,1\}$. Then $g$ is \deff{logspace reducible} to $f$ if there is an ILC function $h:\{0,1\}^*\to\{0,1\}^*$ such that $g=f\circ h$. $f$ is \deff{NL-hard} if every $g\in NL$ is logspace reducible to $f$. $f$ is \deff{NL-complete} if $f\in NL$ and $f$ is NL-hard.\\
Notation: If $g$ is logspace reducible to $f$, write $g\prec_L f$.
\begin{lemma}{}{}
    \begin{itemize}
        \item[(i)] If $h\prec_Lg$ and $g\prec_L f$, then $h\prec_L f$.
        \item[(ii)] If $f$ is NL-complete, $g\in NL$ and $f\prec_L g$, then $g$ is NL-complete. 
    \end{itemize}
\end{lemma}
The proofs are obvious from the previous lemma.\\
\underline{Example of an NL-complete problem}
\begin{proposition}{}{}
    STCONN is NL-complete.
\end{proposition}
\begin{proof}
    Let $f\in NL$. Let $T$ be a NDTM that computes $f$.
    Let $x\in\{0,1\}^*$. Let $G$ be the configuration graph of $T$ with input $x$.
    Then $G$ is easily seen to be implicitly logspace computable.
    But $f(x)=1$ if and only if there is a directed graph in $G$ from $v_{init}$ to $v_{accept}$, so we have a logspace reduction of $f$ to STCONN.
\end{proof}
\subsubsection*{P-completeness}
\textbf{Definition:} A function $f\in P$ is \deff{P-complete} if every $g\in P$ is logspace reducible to $f$.
\begin{lemma}{}{}
    $NL\subset u-AC^1$.
\end{lemma}
\begin{proof}
    Let $f\in NL$, $x\in \{0,1\}^*$, $T$ a NDTM that computes $f$ in logspace.
    Then examining the proof of $P\subset P/poly$, we see that there is a circuit of depth $O(1)$ that inputs a pair of configurations ($\kappa,\kappa'$) and outputs $1$ if and only if $(\kappa,\kappa')$ belongs to the configuration graph.
    Moreover, this circuit is ILC.
    It follows that the adjacency matrix $A$ of $G$ is ILC.
    Also the number of configurations is $2^{O(\log n)}$, so polynomially bounded.
    Let $p(n)$ be a polynomial upper bound.
    Then $f(x)=1\iff$ there is a path of length $\leq p(n)$ from $v_{init}$ to $v_{accept}$.\\
    Given two 01 matrices $A$ and $B$ define their \deff{Boolean product} $AB$ by $(AB)_{ij}=\bigvee_k A_{ik}\wedge B_{kj}$.
    If $A$ and $B$ are square matrices with $1$s on the diagonal then $(AB)_{ij}=1\iff$ there's a path from $i$ to $j$ with first edge in $A$ and second in $B$.\\
    Therefore $(A^r)_{ij}=1$ (if $A$ is a square matrix) if and only if there's a path of length $\leq r$ from $i$ to $j$.
    It follows that we're done if we can find a depth $O(\log n)$ circuit for computing $A^{p(n)}$ (where $A$ is the adj. matrix of $G$)
    But from definition of Boolean product there's a circuit of depth $2$ for computing it so by repeated squaring we get a circuit of depth $O(\log n)$ for computing $A^{p(n)}$.
    It also has polynomial size.
\end{proof}
\begin{corollary}{}{}
    If $f$ is P-complete, then if $f\in u-NC$ then $P=NC$.
\end{corollary}
\begin{proof}
    let $g\in P$. Then $g$ is logspace reducible to $f$, so $\exists h$ ILC such that $g=f\circ h$.
    Since $L\subset u-AC^1\subset u-NC^2$, $h$ can be computed by a logspace uniform family of circuits of depth $O(\log(n)^2)$.
    Combining this with the circuits that compute $f$, we get that $g\in NC$.
\end{proof}
\subsection{Lecture 12}
CIRCUITEVAL is the problem which takes as input a circuit C with $n$ inputs and $x\in\{0,1\}^n$ and outputs $C(x)$.
\begin{proposition}{}{}
    CIRCUITEVAL is $P$-complete.
\end{proposition}
\begin{proof}
    Obviously CIRCUITEVAL is in P.
    If $f\in P$, and $f$ is computable by $T$ in polynomial time, then there is an ILC family $(C_n)$ of circuits that emulate $T$.
    So $f(x)=1\iff$CIRCUITEVAL $(C_{|x|},x)=1$.
    So $f$ is logspace reducible to CIRCUITEVAL.
\end{proof}
\section*{3. Less Obvious Relationships between Complexity Classes}
\subsection*{Lecture 12}
Say that $f:\N\to\N$ is \deff{nice} if 
\begin{itemize}
    \item[(i)] $f(n)\geq n$ for all $n$.
    \item[(ii)] $f$ is increasing.
    \item[(iii)] The function $1^n\mapsto f(n)$ can be computed in time $O(f(n))$. 
\end{itemize}
The next theorem is a weakening of a result called the time hierarchy theorem.
\begin{theo}{}{}
    There exists a polynomial $p$ such that for every nice function $f$, there is a function $\phi$ that can be computed in time $p(f(n))$ such that if $\psi$ is any function that can be computed in time $f(n)$, then there are infinitely many $x$ such that $\phi(x)\neq\psi(x)$.
\end{theo}
The proof uses diagonalization and is in some regards similar to the proof of the halting problem.
\begin{proof}
    The basic idea is as follows: We define $\phi(x)$ to be $1-T(x)$ if $x$ encodes the Turing machine $T$ and $T$ halts in time $f(|x|)$.
    Otherwise let $\phi(x)$ be arbitrary.\\
    \underline{Details:} organize the encoding in such a way that if $s=t0^m$ and one of $s,t$ encodes $T$, then so does the other.
    Suppose that $T$ is some TM that halts in time $f(n)$.
    If $t$ encodes $T$, then $\phi(t)=1-T(t)$, so $\phi$ disagrees with $T$ on $t$.
    But $t$ can be arbitrarily long, so $\phi$ and $T$ disagree infinitely often.\\
    It remains to prove that $\phi$ can be computed in time $p(f(n))$ for some (fixed) polynomial $p$.
    To compute $\phi$, we simulate $T$ using a universal TM and the encoding $t$.
    It's not hard to see that if $T$ takes time $m$ the simulation takes time $O(m^2)$.
    So we run the UTM for time $O(f(m)^2)$ until the simulated machine has taken $f(n)$ steps.
    That is enough to compute $\phi(x)$ when $|x|=n$.
\end{proof}
Let $A:\{0,1\}^*\to\{0,1\}$.
An \deff{oracle Turing machine with oracle $A$} is a TM with an extra \deff{oracle tape}, and at any time it is allowed to "query the oracle" - i.e. if $y$ is the content of the oracle tape, it can obtain the value of $A(y)$ - and this takes one step.\\
Given any uniform complexity class, the "A version" is what you get by replacing the TM by an OTM with oracle $A$.\\
Example: \begin{itemize}
    \item $P^A=$functions computable by an OTM with oracle $A$ in polynomial time.
    \item $NP^A=$functions computable by an NDOTM with oracle $A$ in polynomial time. You can also give the certificate version.
\end{itemize}
We shall now find oracles $A,B$ such that $P^A=NP^A$ and $P^B\neq NP^B$.\\
Let $\text{EXPCOM}(T,x,1^n)=T(x)$ if $T$ computes $T(x)$ in time $2^n$.\\
Claim: $P^{\text{EXPCOM}}=NP^{\text{EXPCOM}}=\text{EXPTIME}$.
\begin{proof}
    Let $f\in \text{EXPTIME}$ and suppose that $f(x)$ can be computed in time $2^{p(|x|)}$ for each $x$ by a TM $T$.
    Given $x$, create $(T,x,1^{p(|x|)})$ on the oracle tape and query the oracle. This shows that $f\in P^{\text{EXPCOM}}$.
    Clearly $P^{\text{EXPCOM}}\subset NP^{\text{EXPCOM}}$ and $g\in P^{\text{EXPCOM}}$ and $q$ a polynomial be such that $f(x)=1\iff \exists y: |y|=q(|x|)$ such that $g(x,y)=1$.
    Each time $g$ queries EXPCOM the oracle tape consists at most polynomially many bits, so we can carry out the computation in time $2^{\text{poly}(n)}$.
    At most polynomially many queries are made so $g\in\text{EXPTIME}$.
    But we can calculate $g(x,y)$ for every $y$ by running $2^{q(n)}$ of these computations.
    So $f\in \text{EXPTIME}$.
    Hence $\NP^{\text{EXPCOM}}\subset \EXPTIME$.
    Putting everything together, $\EXPTIME\subset \text{P}^{\text{EXPCOM}}\subset \text{NP}^{\text{EXPCOM}}\subset \EXPTIME$.
\end{proof}
\begin{proposition}{}{}
    There exists $B$ such that $\text{P}^B\neq \text{NP}^B$.
\end{proposition}
\begin{proof}
    Suppose that we've chosen $B$. Then define a function $\phi$ by $\phi(x)=1\iff \exists y$ such that $|y|=|x|$ and $B(y)=1$.
    Then $\phi\in \NP^B$.

\subsection*{Lecture 13}
Now we shall find  $n_1<n_2<\dots$, sequences $x_1,x_2,\dots$ with $|x_i|=n_i$, and $Y_1\subset Y_2\subset\dots$ finite subsets of $\{0,1\}^*$ and at each stage we should ensure that $B$ is defined on $Y_i$ and (given an enumeration $T_1,T_2,\dots$ of OTMs such that each one appears infinitely often) that if $T_i(x_i)=1$ and $T_i$ halts in time $\leq 2^{\frac{n_i}{10}}$ then $B(y)=0$ for all $y$ of size $n_i$, and if $T_i(x_i)=0$ and $T_i$ halts in time $\leq2^{\frac{n_i}{10}}$ then $\exists y:\;\; |y|=n,$ such that $B(y)=1$.\\
Suppose we have done this up to $i-1$.
Let $n_i$ be bigger than every $|y|$ with $y\in Y_{i-1}$.
Now pick $x_i$ with $|x_i|=n_i$.
Run $T_i$ for $2^{\frac{n_i}{10}}$ steps.
Each time it queries in $B$ with some query $y$ if $B(y)$ has been chosen (i.e. $y\in Y_{i-1}$) then carry on.\\
If $y\not\in Y_{i-1}$ then set $B(y)=0$.
If $T_i$ doesn't halt after $2^{\frac{n_i}{10}}$ steps, then we're done.
If it does and outputs $1$, set $B(y)=0$ for every $y$ with $|y|=n_i$ (This is consistent with our earlier choices).
If it outputs $0$, then pick some $y$ for which $B(y)$ is not yet chosen (possible as $2^{\frac{n_i}{10}}<2^{n_i}$) and set $B(y)=1$.\\
So now if $T$ is any OTM with oracle $B$ it equals $T_i$ for infinitely many $i$, so for infinitely many $x_i$, $T$ either doesn't halt in time $2^{\frac{n_i}{10}}$ or gets $\phi(x_i)$ wrong.
So $\phi\not\in P^B$
\end{proof}
The result above is known as the Baker-Gill-Solovay theorem.\\
A proof is said to \deff{relativize} if it still works when TMs are replaced by OTMs for any given oracle.
So no proof that $P\neq NP$ can relativize, but diagonal arguments do tend to relativize.\\
Here's a corollary of the weak time-hierarchy theorem that we forgot to cover earlier.
\begin{corollary}{}{}
    \[\text{P}\neq\EXPTIME.\]
\end{corollary}
\begin{proof}
    Apply the theorem with $f(n)=n^{\lfloor\log_2n\rfloor}$ then we obtain $\phi$ computable in time $p(f(n))$ (so way subexponential) and if $\psi\in P$ then we can find $\psi'$, computable in time $f(n)$ that agrees with $\psi$ for all sufficiently large $x$.
    Then by the theorem $\psi'$ disagrees with $\phi$ infinitely often, so $\psi\neq\phi$.
\end{proof}
\begin{theo}{Immerman-Szelepcsenyi}{}
    \[\NL=\coNL.\]
\end{theo}
\begin{proof}
    Since STCONN is NL-complete, it's enough to prove that $\text{STCONN}\in\coNL$.\\
    \underline{Claim 1:} If we know how many vertices can be reached from $s$ in $\leq k$ steps and $x$ cannot be reached in $k$ steps then there's a certificate that $x$ cannot be reached.\\
    \textit{proof of claim 1:} Let the vertices of $G$ be $y_1,\dots,y_n$ in lexicographical order of how they're encoded.
    Suppose that $m$ vertices are reachable in $\leq k$ steps.
    Then let $y_{i_1},\dots,y_{i_m}$ be the reachable vertices with $i_1<i_2<\cdots<i_m$.
    The certificate is a path from $s$ to $y_{i_1}$, path from $s$ to $y_{i_2}$,... path from $s$ to $y_{i_m}$.
    In a log amount of space we can check that these paths have length $\leq k$, that $y_{i_1}\prec y_{i_2}\prec\dots\prec y_{i_m}$ and that there are $m$ vertices $y_{i_j}$ and that no $y_{i_j}=x$.\\
    \underline{Claim 2:} If we know how many vertices are reachable with a path of length $k-1$ and $x$ is not reachable in $k$ steps, then there's a certificate of this.\\
    \textit{proof of claim 2:} use the certificate of claim 1 but with $k-1$ replacing $k$, and with "no $y_{i_j}=x$" replaced by "no $y_{i_j}$ is joined to $x$ by a directed edge".\\
    \underline{Claim 3:} For every $k,m$ if exactly $m$ vertices are reachable from $s$ in $\leq k$ steps, then there is a certificate of this.\\
    \textit{proof of claim 3:} Induction on $k$. $k=0$ is trivial. If we know how many vertices are reachable in $\leq k-1$ steps, and $m$ vertices are reachable in $\leq k$ steps, then enumerate the vertices $y_1,\dots,y_n$ in order and for each $y_i$ give either a certificate that it is reachable in $\leq k$ steps (if it is) or a certificate that it isn't (if it isn't) using claim 2.
    We can use this in log space to count how many vertices are reachable in $\leq k$ steps.
\end{proof}
\textit{Remark:} The proof can easily be generalized to larger amounts of space, e.g. to show that $\PSPACE=\NPSPACE$
\subsection*{Lecture 14}
\subsubsection*{Characterizing (non-uniform) NC$^1$}
Recall that a formula is defined inductively as follows: $x_i$ is a formula of size $1$, if $\phi$ is a formula of size $m$, then so is $\neg \phi$, if $\phi_1$, $\phi_2$ are formulas of sizes $m_1,m_2$ then $\phi_1\vee \phi_2$ and $\phi_1\wedge\phi_2$ are formulas of size $m_1+m_2$.
The \deff{formula size} or \deff{formula complexity} of a function $f:\{0,1\}^n\to\{0,1\}$ is the size of a smallest formula that computes $f$.
\begin{proposition}{}{}
    $f\in\text{NC}^1\iff f$ can be computed by a formula of depth $O(\log n)$ (and hence of polynomial size). 
\end{proposition}
\begin{proof}
    "$\Leftarrow$": is trivial.\\
    "$\Rightarrow$": Suppose $f$ can be computed by a fanin $2$ circuit of depth $d$.
    Then $f=\neg g$ or $f_1\wedge f_2$ or $f_1\vee f_2$ for some functions $g,f_1,f_2$ that can be computed by circuits of depth $d-1$.
    So the result follows by induction.
\end{proof}
\begin{lemma}{}{}
    $f$ can be computed by a formula of polynomial size $\iff$ $f$ can be computed by a formula of polynomial size and logarithmic depth.
\end{lemma}
\begin{proof}
    Suppose that $\phi$ is a formula of size $m$ that computes $f$, and that $m>1$.
    \begin{center}
        \includegraphics[width=0.3\textwidth]{fig4.png}
    \end{center}
    Starting at the top of the tree corresponding to $\phi$ walk down to a leaf, at each stage choosing the larger of the two subtrees (or in the case of $\neg$, the unique subtree) just below.
    Then the size of the subformula at each step drops by a factor of at most $2$, so $\phi$ must have a subformula $\psi$ of size between $\frac{m}{3}$ and $\frac{2m}{3}$.
    \begin{center}
        \includegraphics[width=0.3\textwidth]{fig5.png}
    \end{center}
    Let $\phi_0$ and $\phi_1$ be the results of replacing $\psi$ in $\phi$ by $0$ and $1$, respectively.
    Then $\phi$ computes the same function as $(\phi_0\wedge \neg\psi)\vee(\phi_1\wedge \psi)$.\\
    So if $\delta(m)$ is the depth needed for a formula of size $m$, then $\delta(1)=1$ and for $m>1$, $\delta(m)\leq \delta(\frac{2m}{3})+2$.
    So $\delta(m)"\leq"2\log_{3/2}m<4\log_2m$.
\end{proof}
Definition: A \deff{branching program} of width $k$ and length $m$ in $n$ variables $x_1,x_2,\dots,x_n$ is a sequence $(i_t,p_t,q_t)_{t=1}^m$ where $i_t\in\{1,2,\dots,n\}$ and $p_t,q_t$ are functions from $[k]$ to $[k]$.
The \deff{yield} of the program with input $x$ is the function $r_m\circ r_{m-1}\circ\dots\circ r_1$, where $r_t=\begin{cases}
    p_t\;\; x_{i_t}=0\\
    q_t\;\; x_{i_t}=1
\end{cases}$
If $F\subset[k]^{[k]}$, then we can define $f(x)$ to be $1$ if and only if the yield belongs to $F$ on input $x$.
Then the branching program (with $F$) is said to compute $f$.
If all $p_t$, $q_t$ are permutations and $\alpha\in S_k$ is a non-identity permutation, we say that a branching program $\alpha$-computes $f$ if the yield is $\alpha$ when $f(x)=1$ and id when $f(x)=0$.
\begin{theo}{Barrington}{}
    $f\in \NC^1$ if and only if $f$ can be computed by a branching program of bounded width and polynomial length.
\end{theo}
\begin{proof}
    "$\Leftarrow$": an exercise on sheet $3$.\\
    "$\Rightarrow$": Let $f$ be computable by a formula of depth $d$.
    We shall show that $f$ can be computed by a branching program of width $5$ and length $\leq4^d$.\\
    Let $\alpha$ and $\beta$ be 5-cycles and suppose that $f$ is $\alpha$-computable.
    We can find some $\gamma\in S_n$ such that $\gamma\alpha\gamma^{-1}=\beta$.
    So if we replace $p_1,q_1$ by $p_1\gamma^{-1}$ and $q_1\gamma^{-1}$ and $p_m,q_m$ by $\gamma p_m$ and $\gamma q_m$, then the yield changes from $\alpha$ to $\gamma\alpha\gamma^{-1}=\beta$.
    Therefore $f$ is $\alpha$-computable $\iff$ $f$ is $\beta$-computable.\\
    Now let $f=\neg g$.
    Given a branching program that $\alpha$-computes $g$, replace $p_1,q_1$ by $p_1\alpha^{-1}$, $q_1\alpha^{-1}$.
    This shows that $f$ is $\alpha^{-1}$-computable, so if $\alpha$ is a 5-cycle then $f$ is $\alpha$-computable by a branching program of the same length.\\
    Next, suppose that $f=g\wedge h$ and that $g,h$ are $\alpha$-computable by branching programs of length $\leq m$.
    Pick a 5-cycle $\beta$ such that $\alpha\beta\alpha^{-1}\beta^{-1}$ is a 5-cylce. (e.g. if $\alpha=(12345)$, then $\beta=(13542)$ works).
    Now $g$ is $\alpha$-computable and $\alpha^{-1}$-computable and $h$ is $\beta$-computable and $\beta^{-1}$-computable.
    Compose these branching programs:
    $\alpha$-computable $g$ $\circ$ $\beta$-computable $h\circ\alpha^{-1}$-computable $g\circ\beta^{-1}$-computable $h$.
    If either $g(x)=0$ or $h(x)=0$, the yield will be $\beta\beta^{-1}$ or $\alpha\alpha^{-1}$ or id, i.e. id.
    If $g(x)=h(x)=1$, the yield is $\alpha\beta\alpha^{-1}\beta^{-1}$, which is a 5-cycle, so $f$ is $\alpha$-computable by a program of length $\leq 4m$.\\
    By writing $g\vee h$ as $\neg(\neg g\wedge \neg h)$ and combining the two steps above we get a similar conclusion when $f=g\vee h$.
    So the conclusion follows.
\end{proof}
\section*{4. Two Randomized Algorithms}
\subsection*{Lecture 15}
\subsubsection*{Polynomial Identity Testing}
Input: Polynomials $P,Q$ over a field $\F$.\\
Output: $1$ if $P$ and $Q$ are the same polynomial.
\begin{lemma}{(Schwartz-Zippel)}{}
    Let $P$ be a polynomial of total degree $d$ in $n$ variables $x_1,x_2,\dots,x_n$ over a field $\F$ and let $S\subset \F$.
    Then the number of $s\in S^n$ such that $P(s)=0$ is at most $d|S|^{n-1}$.
\end{lemma}
\begin{proof}
    Ex Sheet 3. Induct on $n$.
\end{proof}
Now the algorithm is very simple.
Given a polynomial of degree $d<|\F|$, choose $S\subset \F$ such that $d<|S|$ (if possible).
Then randomly pick $s\in S^n$ and compute $P(s)$ and $Q(s)$ (we assume $P,Q$ are presented in a way that makes this computation efficient).
If $P(s)=Q(s)$ then output $P=Q$.
Otherwise, output $P\neq Q$.
If $P=Q$, the algorithm outputs $P=Q$ with probability $1$.
If $P\neq Q$ it outputs $P\neq Q$ with probability $1-\dfrac{d}{|S|}$ by Schwartz-Zippel on $P-Q$.
If $1-\dfrac{d}{|S|}<\dfrac{1}{2}$, then repeat $k$ times to boost to $1-\left(\dfrac{d}{|S|}\right)^k$ choosing $k$ appropriately such that $1-\left(\dfrac{d}{|S|}\right)^k\geq\dfrac{1}{2}$.\\
This shows that polynomial identity testing is in co-RP.
\subsubsection*{Primality Testing}
The problem takes input $n$ and outputs $1$ $\iff$ $n$ is prime.
We shall show that this is in co-RP.
\begin{lemma}{}{}
    The polynomials $(X+1)^n$ and $X^n+1$ are equal (as polynomials) mod $n$ if and only if $n$ is prime.
\end{lemma}
\begin{proof}
    If $n$ is prime, then $\cho{n}{k}=\dfrac{n!}{k!(n-k)!}$ is a multiple of $n$.
    If $n$ is composite, pick a prime $p$ such that $p\mid n$.
    Then $\dfrac{1}{n}\cho{n}{p}=\dfrac{(n-1)\cdots(n-p+1)}{p!}$ which isn't an integer since $p$ doesn't divide the numerator.
\end{proof}
We can't get anywhere by testing for identity of $(X+1)^n$ and $X^n+1$.
Example: if $n$ is a Carmichael number ($\forall a$, $a^n\equiv a\pmod n$ and $n$ isn't prime) then $(X+1)^n$ and $X^n+1$ take the same values mod $n$.\\
So instead we do this:
\begin{itemize}
    \item Pick a random monic polynomial $Q$ of degree $d$ ($\sim 2\log n$) with coefficients in $\Z/n\Z$.
    \item Calculate $(X+1)^n$ and $X^n+1$ in the ring $\cfrac{\Z/n\Z [x]}{Q(x)}$
    \item If they're equal, output $n$ is prime.
    Else, output $n$ is composite.
\end{itemize}
The second step asks if $(X+1)^n$ and $X^n+1$ are congruent mod $n$,$Q(x)$.\\
We can test this by repeated squaring in time $O(\log n)O(d^2)$, which is polynomial in $\log n$.\\
If $n$ is prime, then $(X+1)^n$ and $X^n+1$ are the same mod $n$, so the same mod $n$,$Q(x)$ for all $Q$.
So the algorithm outputs "$n$ is prime".\\
To deal with the case of composite $n$, we need a lemma.
\begin{lemma}{}{}
    Let $p$ be a prime and let $d$ be a positive integer.
    Then over $\F_p$, $X^{p^d}-X$ is the product of all irreducible polynomials of degree dividing $d$.
\end{lemma}
\begin{corollary}{}{}
    The number of monic irreducible polynomials of degree $d$ over $\F_p$ is $(1-o(1))\dfrac{p^d}{d}$.
\end{corollary}
\begin{proof}
    Let $\phi(k)$ be the number of monic irreducible polynomials of degree $k$.
    Then by the lemma, $p^d=\displaystyle\sum_{k\mid d} k\phi(k)$.
    So by Mobius inversion, \[d\phi(d)=\sum_{k\mid d}\mu(k)p^{\frac{d}{k}}.\]
    The leading term is $p^d$ and remaining terms at most $p^{\frac{d}{2}}$ so the result follows.
\end{proof}
Suppose that $n$ is composite and let $p$ be a prime that divides $n$.
If $\mathbb{P}[\text{algo outputs "n is composite"}]\leq\dfrac{1}{2d}$, then the probability that $Q(x)$ is irreducible and $Q(x)\mid (X+1)^n-X^n-1$ in $\F_p[X]$ is at least $\dfrac{1}{2d}-o(1)$.
But any two distinct monic irreducible polynomials are coprime, so this shows that $d(\dfrac{1}{2d}-o(1))p^d\leq n$.
This is a contradiction if $d\geq 2\log n$.
So if $n$ is composite and $d\geq 2\log n$, then $\mathbb{P}[\text{alg outputs "n is composite"}]\geq\dfrac{1}{2d}-o(1)$.
By repeating $O(d)$ times we can boost this to $\dfrac{1}{2}$.
\end{document}