Revision #1 Authors: Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola

Accepted on: 9th October 2012 13:54

Downloads: 1309

Keywords:

Common presentations of the NP-completeness of SAT suffer

from two drawbacks which hinder the scope of this

flagship result. First, they do not apply to machines

equipped with random-access memory, also known as

direct-access memory, even though this feature is

critical in basic algorithms. Second, they incur a

quadratic blow-up in parameters, even though the

distinction between, say, linear and quadratic time is

often as critical as the one between polynomial and

exponential.

But the landmark result of a sequence of works overcomes

both these drawbacks simultaneously!

\cite{HennieS66,Schnorr78,PippengerF79,Cook88,GurevichS89,Robson91}

The proof of this result is simplified by Van Melkebeek

in \cite[\S 2.3.1]{Melkebeek06}. Compared to previous

proofs, this proof more directly reduces random-access

machines 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 this

simpler proof.

TR12-125 Authors: Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola

Publication: 2nd October 2012 17:10

Downloads: 1964

Keywords:

Common presentations of the NP-completeness of SAT suffer

from two drawbacks which hinder the scope of this

flagship result. First, they do not apply to machines

equipped with random-access memory, also known as

direct-access memory, even though this feature is

critical in basic algorithms. Second, they incur a

quadratic blow-up in parameters, even though the

distinction between, say, linear and quadratic time is

often as critical as the one between polynomial and

exponential.

But the landmark result of a sequence of works overcomes

both these drawbacks simultaneously!

\cite{HennieS66,Schnorr78,PippengerF79,Cook88,GurevichS89,Robson91}

We give the first self-contained rendering of these

results, along the way simplifying and extending the

proof. Compared to previous proofs, ours more directly

reduces random-access machines to circuits, bypassing

sequential Turing machines, and using a simple,

well-known sorting algorithm: Odd-Even Merge sort

\cite{Batcher68}.