ECCC-Report TR12-125https://eccc.weizmann.ac.il/report/2012/125Comments and Revisions published for TR12-125en-usTue, 09 Oct 2012 13:54:33 +0200
Revision 1
| From RAM to SAT |
Emanuele Viola,
Eric Miles,
Zahra Jafargholi,
Hamidreza Jahanjou,
Jaideep Ramachandran
https://eccc.weizmann.ac.il/report/2012/125#revision1Common 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.
Tue, 09 Oct 2012 13:54:33 +0200https://eccc.weizmann.ac.il/report/2012/125#revision1
Paper TR12-125
| From RAM to SAT |
Emanuele Viola,
Eric Miles,
Zahra Jafargholi,
Hamidreza Jahanjou,
Jaideep Ramachandran
https://eccc.weizmann.ac.il/report/2012/125Common 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}.
Tue, 02 Oct 2012 17:10:00 +0200https://eccc.weizmann.ac.il/report/2012/125