Структура данных для запросов минимальных точек продукта

$\mathbb{R}^n$$\langle \cdot, \cdot \rangle$$m$$v_1, v_2, \ldots, v_m$$x \in \mathbb{R}^n$$\min_i \langle x, v_i \rangle$$O(nm)$$n = 2$$O(\log^2 m)$

Единственное, что я могу придумать, это следующее. Непосредственным следствием леммы Джонсона-Линденштрауса является то, что для каждого и распределения в существует линейное отображение (который можно вычислить за времени) так, чтобы . Итак, за время O ((n + m) \ log m) мы можем вычислить$\varepsilon > 0$$\mathcal{D}$$\mathbb{R}^n$$f \colon \mathbb{R}^n \to \mathbb{R}^{O(\log m)}$$O(n \log m)$P r x ∼ D [ ∀ я⟨ Х , v я ⟩ - ε ( | | х | | + | | v я ‖ ) 2 & le ; ⟨ F ( х ) , F ( v я ) ⟩ & le ; ⟨ х , v я ⟩ + ε ( | | х | | + | | V я | | ) 2 ] ≥ 1 - ε O ( ( $\mathrm{Pr}_{x \sim \mathcal{D}}\left[\forall i \quad \langle x, v_i \rangle - \varepsilon (\|x\| + \|v_i\|)^2 \leq \langle f(x), f(v_i)\rangle \leq \langle x, v_i \rangle + \varepsilon (\|x\| + \|v_i\|)^2 \right] \geq 1 - \varepsilon$$O((n + m) \log m)$что-то, что в некотором смысле близко к $\min_i \langle x, v_i \rangle$ для большинства $x$ (по крайней мере, если нормы $\|x\|$ и $\|v_i\|$ малы).

UPD Упомянутая выше граница может быть несколько увеличена до времени запроса $O(n + m)$ если мы используем локальное хеширование. Точнее, мы выбираем $k := O(\frac{1}{\varepsilon^2})$ независимых гауссовских векторов $r_1, r_2, \ldots, r_k$ . Затем мы отображаем $\mathbb{R}^n$ в $\{0,1\}^k$ следующим образом: $v \mapsto (\langle r_1, v \rangle \geq 0, \langle r_2, v \rangle \geq 0, \ldots, \langle r_k, v \rangle \geq 0)$ . Затем мы можем оценить угол между двумя векторами в пределах аддитивной ошибки $\varepsilon$ , вычислив $\ell_1$ расстояние на изображении этого отображения. Таким образом, мы можем оценить точечные произведения в пределах аддитивной ошибки$\varepsilon \|x\| \|v_i\|$за $O(\frac{1}{\varepsilon^2})$ время.

Рассмотрим специальный случай, когда вы просто хотите определить, является ли ваш вектор запроса ортогональным к какому-либо вектору в вашей предварительно обработанной коллекции. (То есть вы хотите определить, если , где обсуждаемые векторы имеют неотрицательные коэффициенты.) Этот случай уже очень интересен.$\min_i \langle x, v_i \rangle = 0$

Предположим, что вы можете ответить на запросы за времени для некоторого , с предварительной обработкой ( степени многочлена не должны зависеть от или или ).$n^{O(1)} m^{1-\delta}$$\delta > 0$$m^{O(1)} n^{O(1)}$$m$$n$$\delta$

В статье «Новый алгоритм оптимального удовлетворения 2-ограничений и его последствия» я заметил, что такая структура данных фактически позволит вам решить CNF-SAT за времени для некоторого , где - количество переменных. Это опровергнет «гипотезу сильного экспоненциального времени», согласно которой для k-SAT требуется, по существу, времени для неограниченного .$2^{\alpha v}$$\alpha < 1$$v$$2^n$$k$

Чтобы понять почему, предположим, что время предварительной обработки ограничено . Рассмотрим формулу CNF с переменными и предложениями. Разобьем множество переменных на две части и размером и соответственно. Перечислите все возможные назначения для переменных в частях (получая и соответственно). Свяжите каждое из этих частичных присвоений с битным вектором где если$(nm)^c$$F$$v$$n$$P_1$$P_2$$v(1-1/(2c))$$v/(2c)$$2^{v(1-1/(2c))}$$2^{v/(2c)}$$A_i$$n$$w_i$$w_i[j]=1$$j$абзац не удовлетворен . Таким образом, у нас есть два списка экспоненциально многих битовых векторов.$F$$A_i$

Обратите внимание, что выполнимо, если существует вектор из назначения на и вектор из назначения на такой что .$F$$w_1$$P_1$$w_2$$P_2$$\langle w_1, w_2 \rangle = 0$

Теперь давай $m=2^{v/(2c)}$ и предварительно обработает предполагаемую структуру данных со всеми векторами из части . По предположению, это занимает времени. Запустите алгоритм запроса для всех векторов из присвоений детали . По предположению, это займет . Пусть .$P_2$$n2^{v/2}$$P_1$$2^{v(1-1/(2c))} \cdot n^{O(1)} m^{1-\delta} = n^{O(1)} 2^{v - \delta v/(2c)}$$\alpha = 1 - \delta/(2c)$

Возможно, можно получить эффективную предварительную обработку и с помощью существующих методов. Самые известные алгоритмы CNF-SAT не исключают этого. (Они получают что-то вроде .) Но вычислить немного сильнее - в этой настройке это будет похоже на решение MAX CNF-SAT.$n^{O(1)} m^{1-1/(\log \log m)}$$2^{n-n/\log n}$$\min_i \langle x, v_i\rangle$

Вот одна идея для точного ответа, на которую, я подозреваю, намекал Чао Сюй. Во-первых, заметим, что мы могли бы также нормализовать x , как указывает Чао. Теперь рассмотрим гиперплоскость h, перпендикулярную направлению x . Цель состоит в том, чтобы найти точку, ближайшую к этой гиперплоскости. По двойственности это соответствует запросу съемки луча в расположении гиперплоскостей, чтобы найти ближайшую плоскость «выше» точки запроса. Так как это может быть предварительно обработано, основной сложностью является местоположение точки, поэтому ваша задача теперь сводится к сложности определения местоположения точки в расположении гиперплоскостей. Используя черенки, это можно сделать за O ( log n ) за n $x$$h$$x$$O(\log n)$$n^d$ Космос.