Известно , что дано nnn - точечное подмножество ℓd2ℓ2d\ell_2^d (то есть, заданный nnn точек в RdRd{\mathbb R}^d с евклидовым расстоянием) можно вставлять их изометрический в ℓ(n2)1ℓ1(n2)\ell^{n\choose 2}_1 . Является ли изометрия вычислимой за (возможно, рандомизированное) полиномиальное время?...
Существует большое количество литературы по «тестированию свойств» - проблеме создания небольшого числа запросов черного ящика к функции чтобы различать два случая:f:{0,1}n→Rf:{0,1}n→Rf\colon\{0,1\}^n \to R является членом некоторого класса функций CfffCC\mathcal{C} является ε -far из каждой...
Rn\mathbb{R}^n⟨⋅,⋅⟩\langle \cdot, \cdot \ranglemmv1,v2,…,vmv_1, v_2, \ldots, v_mx∈Rnx \in \mathbb{R}^nмин я ⟨ х , v я ⟩ mini⟨x,vi⟩\min_i \langle x, v_i \rangleО ( п т )O(nm)O(nm) п = 2 n=2n = 2O ( войти 2 м )O(log2m)O(\log^2 m) Единственное, что я могу придумать, это следующее. Непосредственным...
Предположим, у нас есть неориентированный взвешенный граф G=(V,E,w)G=(V,E,w)G = (V, E, w) (с неотрицательными весами). Предположим, что все кратчайшие пути в GGG единственны. Предположим, у нас есть эти пути (последовательности невзвешенных ребер), но мы не знаем саму G. Можем ли мы создать G ,...
Поскольку термин перегружен, сначала дается краткое определение. Poset - это множество наделенное частичным порядком ≤ . Для двух элементов a , b ∈ X , мы можем определить x ∨ y (join) как их наименьшую верхнюю границу в X и аналогично определить x ∧ y (meet) (join) как наибольшую нижнюю...
Лемма Джонсона-Линденштрауса грубо говорит о том, что для любого набора из точек в существует карта где такой, что для всех : Известно, что подобные выражения невозможны для метрики , но известно, есть ли способ обойти такое низкое значение границы, предлагая более слабые гарантии? Например, может...
Глава Смита в руководстве по логике в области компьютерных наук и другие ссылки описывают, как метрические пространства могут использоваться в качестве областей. Я понимаю, что полные метрические пространства дают уникальные неподвижные точки, но я не понимаю, почему метрические пространства важны....
Срезанная норма вещественной матрицы A = ( a i , j ) ∈ R n × n - максимум по всем I ⊆ [ n ] , J ⊆ [ n ] величины | Σ я ∈ I , J ∈ J я , J | ,||A||C||A||C||A||_CA=(ai,j)∈Rn×nA=(ai,j)∈Rn×nA = (a_{i,j}) \in \mathcal{R}^{n\times n}I⊆[n],J⊆[n]I⊆[n],J⊆[n]I \subseteq [n], J \subseteq...