K-OV: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 44: | Line 44: | ||
| [[CNF-SAT]] || style="text-align:left;" | 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 || 2005 || || [[Reduction from CNF-SAT to k-OV|link]] | | [[CNF-SAT]] || style="text-align:left;" | 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 || 2005 || || [[Reduction from CNF-SAT to k-OV|link]] | ||
|- | |- | ||
| [[OV]] || style="text-align:left;" | | | [[OV]] || style="text-align:left;" | OV is a strict subproblem of k-OV || || || [[Reduction from OV to k-OV|link]] | ||
|- | |- | ||
| [[3-OV]] || style="text-align:left;" | | | [[3-OV]] || style="text-align:left;" | {3}-OV is a strict subproblem of k-OV || || || [[Reduction from 3-OV to k-OV|link]] | ||
|- | |- | ||
|} | |} | ||
Latest revision as of 14:48, 15 February 2023
Description
Given $k$ sets of $d$-dimensional vectors $A_1, A_2, \ldots, A_k$, each of size $n$, does there exist $a_1 \in A_1, a_2 \in A_2, \ldots, a_k \in A_k$ such that $a_1 * a_2 * \ldots * a_k = 0$?
Related Problems
Related: 3-OV, Unbalanced OV
Parameters
$n$: number of vectors per set
$k$: number of sets
$d$: dimension of each vector; $d = omega(log(n))$
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| Exhaustive search | - | $O(d*n^k)$ | $O(k)$ auxiliary | Exact | Deterministic | |
| Reduction to Abboud, Williams, Yu | 2015 | $O(n^{(k-{1}/O(d/log(n)))})$ | Exact | Randomized | Time | |
| Reduction to Chan, Williams | 2016 | $O(n^{(k-{1}/O(d/log(n)))})$ | Exact | Deterministic | Time |
Reductions FROM Problem
| Problem | Implication | Year | Citation | Reduction |
|---|---|---|---|---|
| CNF-SAT | If: to-time: $N^{(k-\epsilon)} poly(m)$ where $m$-dimensional vectors, $k$-OV, $N$ vectors per set Then: from-time: ${2}^{(n-\epsilon')} \poly(m)$ where $\epsilon' = \epsilon/k > {0}$, $n$ variables, $m$ clauses |
2005 | link | |
| OV | OV is a strict subproblem of k-OV | link | ||
| 3-OV | {3}-OV is a strict subproblem of k-OV | link |