Reduction from CNF-SAT to sensitive incremental ST-Reach
Revision as of 11:19, 15 February 2023 by Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: sensitive incremental ST-Reach == Description == == Implications == assume: SETH<br/>then: let $\epsilon > {0}$, $t \in \mathbb{N}$, there exists no algorithm for target with preprocessing time $O(n^t)$, update time $u(n)$ and query time $q(n)$, such that $max\{u(n),q(n)\}=O(n^{1-\epsilon})$ with constant sensitivity $K(\epsilon,t)$ == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Co...")
FROM: CNF-SAT TO: sensitive incremental ST-Reach
Description
Implications
assume: SETH
then: let $\epsilon > {0}$, $t \in \mathbb{N}$, there exists no algorithm for target with preprocessing time $O(n^t)$, update time $u(n)$ and query time $q(n)$, such that $max\{u(n),q(n)\}=O(n^{1-\epsilon})$ with constant sensitivity $K(\epsilon,t)$
Year
2017
Reference
Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity problems. arXiv preprint arXiv:1703.01638.