

\addtolength{\hoffset}{-1.7cm}
\addtolength{\voffset}{-1.5cm}
\addtolength{\textwidth}{3.4cm}
\addtolength{\textheight}{2.5cm}

\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{enumerate}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{fancyvrb}
\usepackage{multirow}
\usepackage{relsize}
\usepackage{url}
\usepackage{tikz}
\usetikzlibrary{arrows, petri,topaths}
%\usepackage{tkz-berge}

\usepackage[T1]{fontenc}

\usepackage[noend]{algorithmic}
\usepackage{algorithm}
\renewcommand{\thealgorithm}{}
\floatname{algorithm}{}

%%%%%%%%%%%%%for graph
\usetikzlibrary{automata,positioning}
\tikzset{initial text={}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5


\renewcommand*{\thefootnote}{\fnsymbol{footnote}}

\newcounter{mycount}

\usepackage{lastpage}  
\usepackage{fancyhdr}
\pagestyle{fancy}
\fancyhf{}
\renewcommand{\headrulewidth}{0pt}
\lhead{\tiny \underline{CSIE 5046: Topics in complexity theory (Sem. 2, 2021/2022)}}
\cfoot{\footnotesize \thepage/\pageref{LastPage}}
\rhead{\tiny \underline{\fulltitle}}

\newcommand{\lesson}{0}
\newcommand{\lessontitle}{To be defined on each lesson}
\newcommand{\fulltitle}{Lesson \lesson: \lessontitle}

\renewcommand{\themycount}{\lesson.\arabic{mycount}}

%\renewcommand{\thefootnote}{\fnsymbol{footnote}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%% LIST OF ENVIRONMENTS %%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newtheorem{defn}[mycount]{Definition}
\newtheorem{eg}[mycount]{Example}
\newtheorem{rem}[mycount]{Remark}

\newtheorem{theorem}[mycount]{Theorem}
\newtheorem{lemma}[mycount]{Lemma}
\newtheorem{proposition}[mycount]{Proposition}
\newtheorem{corollary}[mycount]{Corollary}
\newtheorem{problem}[mycount]{Problem}
\newtheorem{question}[mycount]{Question}

\newtheorem{claim}{Claim}
\newtheorem{fact}{Fact}
\newtheorem{observation}{Observation}

\newenvironment{definition}{\defn \em }
 {\vspace{0.9 em}} 

\newenvironment{remark}{\rem \em}{\vspace{0.5 em}}

\newenvironment{example}{\eg \em}{\vspace{0.3 em}}{\vspace{0.5 em}}

\newenvironment{proof}
{\noindent {\bf Proof.}}{\QED {\vspace{1.0 em}}}

\newenvironment{note}
{\vspace{0.3 em} \noindent {\bf Note.}}{\vspace{0.5 em}}

%\def\squareforqed{$\blacksquare$}
\def\squareforqed{$\qed$}
\def\QED{\ifmmode\squareforqed\else{\unskip\nobreak\hfil
\penalty50\hskip1em\null\nobreak\hfil\squareforqed
\parfillskip = 0pt\finalhyphendemerits = 0\endgraf}\fi}

\newenvironment{consequence}
{\vspace{0.5 em} \noindent {\bf Corollary \em} }{\vspace{0.5 em}}

\def\filledbox{\vrule height 1.8ex width .8ex depth 0ex }
\newcommand{\qed}{\filledbox}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%% MACROS FOR SYMBOLS %%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\ans}{\mbox{\bf Ans:}}

\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}

\newcommand{\myT}{{\sf true}}
\newcommand{\myF}{{\sf false}}

\newcommand{\acc}{{\sf ACCEPT}}
\newcommand{\rej}{{\sf REJECT}}

\newcommand{\qeq}{\stackrel{\textsf{\tiny ?}}{=}}
\newcommand{\defeq}{\stackrel{\textsf{\tiny def}}{=}}


\newcommand{\cA}{\mathcal{A}}
\newcommand{\cB}{\mathcal{B}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cE}{\mathcal{E}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cG}{\mathcal{G}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cR}{\mathcal{R}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\cU}{\mathcal{U}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\cZ}{\mathcal{Z}}


\newcommand{\va}{\bar{a}}
\newcommand{\vb}{\bar{b}}
\newcommand{\vc}{\bar{c}}
\newcommand{\vd}{\bar{d}}
\newcommand{\vm}{\bar{m}}
\newcommand{\vp}{\bar{p}}
\newcommand{\vt}{\bar{t}}
\newcommand{\vv}{\bar{v}}
\newcommand{\vu}{\bar{u}}
\newcommand{\vw}{\bar{w}}
\newcommand{\vx}{\bar{x}}
\newcommand{\vy}{\bar{y}}
\newcommand{\vz}{\bar{z}}

\newcommand{\vZ}{\bar{Z}}

\newcommand{\bbF}{\mathbb{F}}
\newcommand{\bbN}{\mathbb{N}}
\newcommand{\bbQ}{\mathbb{Q}}
\newcommand{\bbR}{\mathbb{R}}
\newcommand{\bbZ}{\mathbb{Z}}


\newcommand{\sA}{\textsf{A}}
\newcommand{\sE}{\textsf{E}}
\newcommand{\sL}{\textsf{L}}
\newcommand{\sQ}{\textsf{Q}}

\newcommand{\sfL}{\textsf{\underline{L}}}
\newcommand{\sfR}{\textsf{\underline{R}}}
\newcommand{\sfW}{\textsf{\underline{W}}}

\renewcommand{\iff}{\leftrightarrow}

\newcommand{\Left}{\texttt{Left}}
\newcommand{\Right}{\texttt{Right}}
\newcommand{\Stay}{\texttt{Stay}}
\newcommand{\Write}{\texttt{Write}}
\newcommand{\Move}{\texttt{Move}}


\newcommand{\blank}{\sqcup}
\newcommand{\qacc}{q_{\textsf{acc}}}
\newcommand{\qrej}{q_{\textsf{rej}}}
\newcommand{\tblank}{\tilde{\blank}}
\newcommand{\qquery}{q_{\textsf{query}}}
\newcommand{\qyes}{q_{\textsf{yes}}}
\newcommand{\qno}{q_{\textsf{no}}}

\newcommand{\floor}[1]{\lfloor#1\rfloor}

\newcommand{\ttL}{\texttt{L}}
\newcommand{\ttR}{\texttt{R}}
\newcommand{\ttS}{\texttt{S}}
\newcommand{\bcomma}{\texttt{,}}

\newcommand{\per}{\textup{per}}
\newcommand{\poly}{\textsf{poly}}
\newcommand{\unary}{\textsf{unary}}

\newcommand{\gf}{\textsf{GF}}

\newcommand{\height}{\textsf{\textup{height}}}
\newcommand{\depth}{\textsf{\textup{depth}}}
\newcommand{\stars}{\textsf{\textup{stars}}}

\newcommand{\pr}{\mathbf{Pr}}
\newcommand{\prarg}[1]{\pr [\ #1 \ ]}
\newcommand{\prargbig}[1]{\pr \Big[\ #1 \ \Big]}
\newcommand{\prdist}[2]{\pr_{#1}[\ #2\ ]}
\newcommand{\Exp}{\mathbf{Exp}}

%%%%%% complexity class 

\newcommand{\class}[1]{\textbf{\textup{#1}}}

\newcommand{\size}{\textsc{size}}

\newcommand{\dtime}{\textsc{Dtime}}
\newcommand{\ntime}{\textsc{Ntime}}
\newcommand{\atime}{\textsc{Atime}}

\newcommand{\dspace}{\textsc{Dspace}}
\newcommand{\nspace}{\textsc{Nspace}}
\newcommand{\aspace}{\textsc{Aspace}}
\newcommand{\conspace}{\textrm{\textup{co\textsc{Nspace}}}}

\newcommand{\ls}{\class{L}}
\newcommand{\nls}{\class{NL}}
\newcommand{\conls}{\class{coNL}}
\newcommand{\pt}{\class{P}}
\newcommand{\npt}{\class{NP}}
\newcommand{\conpt}{\class{coNP}}
\newcommand{\ps}{\class{PSPACE}}
\newcommand{\nps}{\class{NPSPACE}}
\newcommand{\conps}{\class{coNPSPACE}}
\newcommand{\expt}{\class{EXP}}
\newcommand{\nexpt}{\class{NEXP}}
\newcommand{\aexpt}{\class{AEXP}}
\newcommand{\conexpt}{\class{coNEXP}}
\newcommand{\exps}{\class{EXPSPACE}}

\newcommand{\sharpp}{\sharp\pt}
\newcommand{\psharpp}{\pt^{\sharpp}}

\newcommand{\sigmap}[1]{\mathbf{\Sigma}^{p}_{#1}}
\newcommand{\pip}[1]{\mathbf{\Pi}^{p}_{#1}}
\newcommand{\pht}{\class{PH}}

\newcommand{\als}{\class{AL}}
\newcommand{\apt}{\class{AP}}
\newcommand{\aps}{\class{APSPACE}}

\newcommand{\fpt}{\class{FP}}
\newcommand{\ppt}{\class{PP}}

\newcommand{\ppoly}{\pt_{\textup{\!\!/\poly}}}
\newcommand{\nc}{\class{NC}}
\newcommand{\ac}{\class{AC}}

\newcommand{\bpp}{\class{BPP}}
\newcommand{\zpp}{\class{ZPP}}
\newcommand{\rp}{\class{RP}}
\newcommand{\corp}{\class{coRP}}

\newcommand{\ip}{\class{IP}}
\newcommand{\ma}{\class{MA}}
\newcommand{\am}{\class{AM}}

\newcommand{\paritypt}{\oplus\pt}


%%%%%% problem names

\newcommand{\prob}[1]{\textsf{\textup{#1}}}

\newcommand{\cycle}{\prob{CYCLE}}
\newcommand{\reach}{\prob{REACH}}
\renewcommand{\path}{\prob{PATH}}

\newcommand{\circuiteval}{\prob{CIRCUIT-EVAL}}

\newcommand{\sat}{\prob{SAT}}
\newcommand{\threesat}{\prob{3-SAT}}
\newcommand{\threecolor}{\prob{3-COL}}
\newcommand{\indset}{\prob{IND-SET}}
\newcommand{\clique}{\prob{CLIQUE}}
\newcommand{\vertexcover}{\prob{VERT-COVER}}
\newcommand{\domset}{\prob{DOM-SET}}

\newcommand{\noniso}{\prob{NON-ISO}}
\newcommand{\nonsq}{\prob{NON-SQ}}


\newcommand{\sigmasat}[1]{\Sigma_{#1}\textsf{\textup{-SAT}}}
\newcommand{\pisat}[1]{\Pi_{#1}\textsf{\textup{-SAT}}}

\newcommand{\tqbf}{\prob{TQBF}}

\newcommand{\parity}{\prob{PARITY}}

\newcommand{\usat}{\prob{USAT}}

\newcommand{\halt}{\prob{HALT}}
\newcommand{\pcp}{\prob{PCP}}

\newcommand{\sharpsat}{\sharp\sat}
\newcommand{\sharpcycle}{\sharp\cycle}

\newcommand{\perm}{\prob{PERM}}
\newcommand{\zerooneperm}{\prob{0|1-PERM}}

\newcommand{\paritysat}{\oplus\sat}


%%%%%%%%% Algorithm macro

\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Task:}}

\newcommand{\algoe}[1]{\langle \texttt{#1} \rangle}
\newcommand{\algoi}[1]{\text{\bf #1}}

%%%%%%%%% Some labels

\newcommand{\sfRed}{\textsf{Red}}
\newcommand{\sfBlue}{\textsf{Blue}}
\newcommand{\sfGreen}{\textsf{Green}}


%%%%%% color

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%% my colours %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\colorlet{darkgreen}{green!50!black}

\definecolor{mygreen}{rgb}{0.2,0.8,0.2}
\definecolor{myblue}{rgb}{0.0,0.0,0.61}
\definecolor{lightblue}{rgb}{0.8,0.8,0.95}

\definecolor{celadon}{rgb}{0.67, 0.88, 0.69}
\definecolor{lavenderblush}{rgb}{1.0, 0.94, 0.96}
\definecolor{magicmint}{rgb}{0.67, 0.94, 0.82}

\definecolor{palegreen}{rgb}{0.88, 0.98, 0.88}

\definecolor{bluebell}{rgb}{0.64, 0.64, 0.82}
\definecolor{almond}{rgb}{0.94, 0.87, 0.8}

\definecolor{aquamarine}{rgb}{0.5, 1.0, 0.83}
\definecolor{chromeyellow}{rgb}{1.0, 0.65, 0.0}
\definecolor{peach-orange}{rgb}{1.0, 0.8, 0.6}
\definecolor{peach-yellow}{rgb}{0.98, 0.87, 0.68}
\definecolor{selectiveyellow}{rgb}{1.0, 0.73, 0.0}
\definecolor{pink-orange}{rgb}{1.0, 0.6, 0.4}
\definecolor{beige}{rgb}{0.96, 0.96, 0.86}

\definecolor{cadmiumorange}{rgb}{0.93, 0.53, 0.18}
\definecolor{coolblack}{rgb}{0.0, 0.18, 0.39}
\definecolor{darkmagenta}{rgb}{0.55, 0.0, 0.55}
\definecolor{blizzardblue}{rgb}{0.67, 0.9, 0.93}



\definecolor{pastelorange}{rgb}{1.0, 0.7, 0.28}

\definecolor{maroon}{rgb}{0.5, 0.0, 0.0}
\definecolor{internationalkleinblue}{rgb}{0.0, 0.18, 0.65}
\definecolor{ballblue}{rgb}{0.13, 0.67, 0.8}
\definecolor{babyblue}{rgb}{0.54, 0.81, 0.94}
\definecolor{columbiablue}{rgb}{0.61, 0.87, 1.0}
\definecolor{darkscarlet}{rgb}{0.34, 0.01, 0.1}
\definecolor{rosewood}{rgb}{0.4, 0.0, 0.04}

\definecolor{crimsonglory}{rgb}{0.75, 0.0, 0.2}





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%% END MACROS FOR SYMBOLS %%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



