Common presentations of the NP-completeness of SAT sufferfrom two drawbacks which hinder the scope of thisflagship result. First, they do not apply to machinesequipped with random-access memory, also known asdirect-access memory, even though this feature iscritical in basic algorithms. Second, they incur aquadratic blow-up in parameters, even though thedistinction between, say, linear and quadratic time isoften as critical as the one between polynomial andexponential.

But the landmark result of a sequence of works overcomesboth these drawbacks simultaneously!\cite{HennieS66,Schnorr78,PippengerF79,Cook88,GurevichS89,Robson91}

The proof of this result is simplified by Van Melkebeekin \cite[\S 2.3.1]{Melkebeek06}. Compared to previousproofs, this proof more directly reduces random-accessmachines to SAT, bypassing sequential Turing machines,and using a simple, well-known sorting algorithm:Odd-Even Merge sort \cite{Batcher68}.

In this work we give a self-contained rendering of thissimpler proof.