Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Jaideep Ramachandran:

TR12-125 | 2nd October 2012
Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola

From RAM to SAT

Revisions: 1

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 ... more >>>

ISSN 1433-8092 | Imprint