View source for Reduction from CNF-SAT to Local Alignment

FROM: [[CNF-SAT]] TO: [[Local Alignment]]

== Description == 



== Implications == 

if: to-time: $N^{2-\epsilon}$ for some $\epsilon > {0}$ on two binary strings of length $N$<br/>then: from-time: ${2}^{(n-\epsilon')}$ for some $\epsilon' > {0}$

== Year == 

2014

== Reference == 

Abboud, Amir, Virginia Vassilevska Williams, and Oren Weimann. "Consequences of faster alignment of sequences." In International Colloquium on Automata, Languages, and Programming, pp. 39-51. Springer, Berlin, Heidelberg, 2014.

https://link.springer.com/chapter/10.1007/978-3-662-43948-7_4