Reduction from CNF-SAT to k-OV: Revision history

Jump to navigation Jump to search

Diff selection: Mark the radio buttons of the revisions to compare and hit enter or the button at the bottom.
Legend: (cur) = difference with latest revision, (prev) = difference with preceding revision, m = minor edit.

    15 February 2023

    • curprev 12:1812:18, 15 February 2023‎ Admin talk contribs‎ 466 bytes +466‎ Created page with "FROM: CNF-SAT TO: k-OV == Description == == Implications == If: to-time: $N^{(k-\epsilon)} poly(m)$ where $m$-dimensional vectors, $k$-OV, $N$ vectors per set<br/>Then: from-time: ${2}^{(n-\epsilon')} \poly(m)$ where $\epsilon' = \epsilon/k > {0}$, $n$ variables, $m$ clauses == Year == 2005 == Reference == Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357–365, 2005."
Retrieved from "https://algorithm-wiki.csail.mit.edu/wiki/Reduction_from_CNF-SAT_to_k-OV"