Сложность тестирования, если два набора из

Представьте, что у нас есть два размера $m$ наборов точек $X,Y\subset \mathbb{R}^n$ . Какова (временная) сложность тестирования, если они отличаются только ротацией? : существует матрица вращения $OO^T=O^TO=I$ такая, что $X=OY$ ?

Здесь возникает проблема представления реальных значений - для простоты предположим, что существует (короткая) алгебраическая формула для каждой координаты, так что стоимость основных арифметических операций может быть принята за O (1).

Основной вопрос, если эта проблема в P?

Хотя на первый взгляд эта проблема может показаться простой - обычно достаточно проверить нормы точек и локальных отношений, таких как углы, есть неприятные примеры, в которых она, например, эквивалентна проблеме изоморфизма графов .

В частности, глядя на собственные пространства матрицы смежности сильно регулярных графов (SRG), мы можем дать ей геометрическую интерпретацию . Ниже приведен простейший пример - два 16 вершинных SRG, которые локально выглядят одинаково, но не изоморфны:

$A-2I$ $O(6)$ $X\subset \mathbb{R}^6$ $|X|=16$ $Y$ $X$ $Y$

Сложность состоит в том, что все эти точки находятся в сфере и воссоздают исходные отношения: все соседи (6 здесь) находятся под фиксированным углом <90 градусов, все несоседние (9 здесь) под другим фиксированным углом> 90 градусов, как на схеме картинка выше.

Таким образом, тестирование, основанное на норме и локальных углах, возвращает нас к проблеме изоморфизма графа ... но геометрическая интерпретация позволяет работать с глобальными свойствами, такими как инварианты вращения.

$n(n-1)/2$

Обычно мы можем определить инварианты вращения - вопрос состоит в том, чтобы построить полный набор инвариантов вращения: полностью определить набор вращения по модулю.

$x^T A x$ $Tr(A^k)$ $k=1,\ldots,n$ $k$ каждый приведенный ниже график соответствует одному инварианту вращения степени 1,2,3,4 :

$p(z)=\prod_{x\in X} (x\cdot (z-x))$

p (z) = \sum_{x \in X} (x \cdot z - a)^{2} (x \cdot z - b)^{2} (x \cdot z - c)^{2}

$p(z)=\sum_{x\in X} (x\cdot z -a)^2 (x\cdot z -b)^2 (x\cdot z -c)^2$

a, b, c

$a,b,c$

Так можем ли мы проверить, отличаются ли два полинома степени 6 только вращением за полиномиальное время? Если это так, то изоморфизм графов для SRG находится в P.

Существуют ли более жесткие примеры (для тестирования, если два набора отличаются только по ротации), чем от SRG? Я сомневаюсь в этом, учитывая квазиполиномиальную верхнюю границу благодаря Бабаю (?)

Обновление : мне было указано сходство с (решенной) проблемой ортогональных прокрустов :

min_{O : O^{T} O = I} ‖ O A - B ‖_{F} achieved for O = U V^{T}, where B A^{T} = U D V^{T}

$\min_{O:O^TO=I} \|OA-B\|_F \quad\textrm{achieved for}\quad O=UV^T,\quad\textrm{ where}\quad BA^T=UDV^T$

из разложения по сингулярности. Мы могли бы построить эти матрицы из наших точек, однако, это потребовало бы знания порядка - которого мы не знаем, а ихвозможности. $m!$

Мы могли бы попробовать, например, Монте-Карло или генетический алгоритм: переключение некоторых точек и тестирование улучшения расстояния с использованием приведенной выше формулы, однако я подозреваю, что такой эвристический алгоритм может иметь экспоненциальное число локальных минимумов (?)

cc.complexity-theory complexity-classes graph-isomorphism computational-geometry high-dimensional-geometry Ярек Дуда
источник

Что ж, убийственные примеры для практических алгоритмов изоморфизма графов не обязательно являются SRG. Я рассмотрел здесь две работы Дэниела Нойена и Паскаля Швейцера , в которых приводятся самые сложные на данный момент примеры. В моем обсуждении утверждается, что «мультипедовая конструкция ... в основном нормальная конструкция CFI, применяемая к неориентированному многогранному гиперграфу». Эта конструкция дополнительно модифицируется, чтобы сделать ее жесткой, что устраняет все автоморфизмы. До этого не было SRG, но после точно не будет SRG.

Томас Климпел

Я думаю, что поиск основных компонентов наборов точек и их проверка могли бы помочь, поскольку преобразование PCA обладает довольно хорошими свойствами.

FazeL

ThomasKlimpel, не могли бы вы сказать что-нибудь о собственных пространствах этих других сложных примеров? @FazeL, собственные значения корреляционной матрицы из PCA являются примерами инвариантов вращения - необходимые условия, отличающиеся только вращением (тривиально для SRG). Задача состоит в том, чтобы получить достаточное условие, например, через полный базис инвариантов вращения - полностью определить множество (или полином) вращение по модулю. Вот общая конструкция для полиномов: arxiv.org/pdf/1801.01058 , вопрос в том, как выбрать достаточное количество (известных) независимых инвариантов?

Ярек Дуда

Эти графики уже раскрашены. Для фиксированного есть цвета, для которых узла имеют этот цвет, и цвета, для которых 2 узла имеют этот цвет. В терминах собственных пространств это означает, что вы получаете много собственных пространств измерения и даже больше собственных пространств измерения . По крайней мере, так происходит, если конструкция CFI применяется к k-регулярному неориентированному графу. (Но не волнуйтесь, изоморфизм SRG также является открытой проблемой.)

k

$k$

2^{k - 1}

$2^{k-1}$

2^{k - 1}

$2^{k-1}$

2

$2$

Томас Климпел

Собственные пространства размерности могут на самом деле разделиться на еще меньшие собственные пространства, поскольку даже для SRG у нас есть более 1 собственное пространство, но логика выше предполагает, что существует только одно собственное пространство. Посмотрите на рисунок 4.2 в более короткой (более теоретической) статье, чтобы увидеть / понять, как выглядят эти графики.

2^{k - 1}

$2^{k-1}$

Томас Климпел

Я думаю, что это открыто. Обратите внимание, что если вместо проверки эквивалентности при вращениях вы запрашиваете эквивалентность по общей линейной группе, то уже проверяется эквивалентность многочленов степени три GI-hard ( Agrawal-Saxena STACS '06 , свободно доступная версия автора ) и фактически находится по адресу менее сложно, чем проверка изоморфизма алгебр. Теперь, GI-hardness не является доказательством того, что ваша проблема не в , так как на самом деле весь ваш вопрос состоит в том, можем ли мы поместить GI в $\mathsf{P}$ $\mathsf{P}$ подходом, который вы предлагаете. Однако тот факт, что эквивалентность кубической формы уже кажется значительно сложнее, чем GI (например, мы до сих пор не знаем, находится ли изоморфизм алгебры в квазиполигональном времени, в отличие от GI), говорит о том, что (а) люди думали об этом подходе и (б) его все еще открыт

Хотя я не знаю наверняка, если аналогичные результаты верны для ортогональной группы, я был бы удивлен, если бы они не выполнялись (особенно если вы переходите от степени 3 к степени 6).

Джошуа Грохов
источник

Спасибо, я вижу, мне есть что читать. Стало ли трудным тестирование, отличающееся вращением полиномов, для третьей степени? Количество коэффициентов равно O (dim ^ степень), вращение имеет dim (dim-1) / 2 коэффициента, поэтому полное описание вращения по модулю должно быть дано O (dim ^ степени) независимыми инвариантами вращения. Я знаю, как построить инварианты вращения ( arxiv.org/pdf/1801.01058 ), условие независимости кажется трудным доказать, но высокая зависимость кажется маловероятной (?)

Ярек Дуда

@JarekDuda: Тот же аргумент, который вы приводите в своем комментарии, будет применяться к общей линейной эквивалентности, за исключением того, что вместо коэффициентов вас будет , но оба они являются . ..Зависимость между инвариантами часто является очень глубоким вопросом. Кроме того, вопрос не только в том, сколько независимых инвариантов вам нужно, но (а) вы можете вычислить, какие инварианты вам нужны в поли-времени, и (б) вы можете даже вычислить значение каждого такого инварианта в поли-времени?

(\binom{d i m}{2})

$\binom{dim}{2}$

d i m^{2}

$dim^2$

Θ (d i m^{2})

$\Theta(dim^2)$

Джошуа Грохоу

Конечно, если бы только была возможность построить большое количество инвариантов - хотя я не знаю, верно ли это для других типов эквивалентности (?), Для инвариантов вращения есть конструкция, где каждый граф дает один инвариант, и существуют систематические конструкции большие числа, например, по аналогии с циклами длины k для Tr (A ^ k), инвариантных для полинома степени 2 x ^ T Ax. Для многочлена с фиксированной степенью мы можем получить достаточное количество (или намного больше) инвариантов за многократное время - остающаяся проблема состоит в том, чтобы обеспечить достаточное количество независимых среди них.

Ярек Дуда

Сложность тестирования, если два набора из

Ответы: