Пример, в котором эквивалентность проста, но трудно найти представителя класса

Предположим, у нас есть класс объектов (например, графы, строки) и отношение эквивалентности для этих объектов. Для графов это может быть изоморфизм графов. Для строк мы можем объявить две строки эквивалентными, если они являются анаграммами друг друга.

Я заинтересован в вычислении представителя для класса эквивалентности. То есть я хочу функцию f () такую, чтобы для любых двух объектов x, y, f (x) = f (y) тогда и только тогда, когда x и y эквивалентны. (*)

Для примера анаграмм f (s) может сортировать буквы в строке, т.е. f ('cabac') = 'aabcc'. Для изоморфизма графа мы могли бы взять f (G) как граф G ', который изоморфен G и является лексикографически первым графом, обладающим этим свойством.

Теперь вопрос: есть ли пример, когда проблема определения того, эквивалентны ли два элемента, является «легкой» (с временным разрешением), в то время как найти представителя сложно (т. Е. Не существует многополосного алгоритма для вычисления f (), который удовлетворяет ( *)).

Хорошо, как насчет: числа и y эквивалентны, если либо x = y , либо оба x и y имеют разложения x = p q и y = p r, где p , q и r все простые и$x$$y$$x=y$$x$$y$$x=pq$$y=pr$$p$$q$$r$ . То есть: произведения двух простых чисел эквивалентны, когда они имеют наименьший простой множитель; другие числа эквивалентны только себе.$p < \min(q,r)$

Легко проверить, эквивалентны ли два разных числа: вычислить их gcd, проверить, является ли оно нетривиальным, проверить, меньше ли gcd кофакторов, и проверить, являются ли все gcd и его кофакторы простыми.

Но не очевидно, как вычислить репрезентативную функцию за полиномиальное время, и если вы добавите требование, что f ( $f$ должно быть эквивалентно x, то любая репрезентативная функция позволит намбольшинство произведений двух простых чисел (каждое из которых не является не свой представитель).$f(x)$$x$

Два целых числа по модулю п эквивалентны , если х 2 ≡ у 2 мод п . Если бы можно было легко вычислить представителя класса для этой функции, то факторинг может быть выполнен за вероятностное полиномиальное время.$x,y$$n$$x^{2} \equiv y^{2}$$n$

В общем, такой пример будет означать , что . Предположим, что R - отношение эквивалентности, разрешимое за полиномиальное время. Затем с помощью лексикографического поиска с использованием оракула N P можно найти наименьший лексикографический элемент в классе эквивалентности любой строки. Если P $P \neq NP$$R$$NP$ , это становится полиномиальным временем, поэтому вы можете использовать лексикографически наименее эквивалентную строку в качестве представителя класса. Это наблюдение изначально принадлежит Блассу и Гуревичу [1].$P=NP$

Такой пример также подразумевал бы (и, следовательно, в частности, P ≠ U P ).$UP \not\subseteq BQP$$P \neq UP$

Вопрос, который вы задали, это то, что мы обозначаем в нашей статье с Лэнсом Фортнау [2]. Эта статья также включает в себя результаты, которые я изложил здесь, а также пример хеш-функций, указанных Питером Шором, несколько других возможных примеров, а также связанные результаты и вопросы.$PEq =? Ker(FP)$

[1] Бласс А., Гуревич Ю. Соотношения эквивалентности, инварианты и нормальные формы . SIAM J. Comput. 13 (4): 682-689, 1984.

[2] Fortnow, L. и Grochow, JA. Сложность классов проблем эквивалентности вновь . Поставить в известность. и компьютер. 209 (4): 748-763, 2011. Также доступно по архиву .

Должен ли «представитель» находиться в классе эквивалентности?

Если это так, то возьмите любую криптографически сильную хеш- функцию с сопротивлением столкновению.$f$

Пусть если f ( x ) = f ( y $x \simeq y$$f(x) = f(y)\,$, Легко проверить, эквивалентны ли две вещи, но если, учитывая , вы можете найти канонический прообраз h , то вы можете найти две строки x и y, такие что f ( x ) = f ( y $f(x) = h$$h$$x$$y$$f(x)=f(y)\,$, Это должно быть трудно (вот что означает сопротивление столкновению).

Конечно, компьютерные ученые не могут доказать, что существуют криптографически сильные хеш-функции с сопротивлением столкновению, но у них есть ряд кандидатов.

Во-первых, то, что вы действительно запрашиваете, обычно называется полным инвариантом. Каноническая или нормальная форма также требует, чтобы $f(x)$ был эквивалентен $x$ для всех $x$ . (Запрашивать «представителя» немного двусмысленно, поскольку некоторые авторы могут подразумевать, что это включает условие канонической формы.)

Во-вторых, пожалуйста, прости бесстыдную саморекламу, но это как раз один из вопросов, над которым мы с Фортнау работали [1]. Мы показали, что если каждое отношение эквивалентности, которое может быть решено в $\mathsf{P}$ также имеет полный инвариант в $\mathsf{FP}$ , то случаются плохие вещи. В частности, это будет означать $\mathsf{UP} \subseteq \mathsf{BQP}$ . Если верна многообещающая версия этого утверждения (см. Теорему 4.6), то $\mathsf{NP} \subseteq \mathsf{BQP} \cap \mathsf{SZK}$ и $\mathsf{PH} = \mathsf{AM}$ .

Теперь, если вы на самом деле хотите каноническую форму (представитель каждого класса эквивалентности, который также входит в класс эквивалентности), мы покажем, что вещи еще хуже. То есть, если каждое отношение эквивалентности, разрешимое в полиномиальном времени, имеет каноническую форму с временным разложением, то:

• Целые числа могут быть учтены в вероятностном поли времени
• Бесстолкновительные хеш-функции, которые можно оценить в $\mathsf{FP}$ , не существуют.
• $\mathsf{NP} = \mathsf{UP} = \mathsf{RP}$ (следовательно,$\mathsf{PH} = \mathsf{BPP}$ )

Для большинства из этих утверждений об отношениях эквивалентности есть и оракулы, идущие в обе стороны, благодаря нам, а также Блассу и Гуревичу [2].

Если вместо «любого» представителя вы запрашиваете лексикографически наименьший элемент в классе эквивалентности, то обнаружение лексикографически наименьшего элемента в классе эквивалентности может быть $NP$ трудным (фактически $P^{NP}$ -hard) - даже если отношение имеет полиномиальную каноническую форму [2].

[1] Лэнс Фортноу и Джошуа А. Грохов. Классы сложности проблем эквивалентности вновь . Поставить в известность. и компьютер. 209: 4 (2011), 748-763. Также доступно как arXiv: 0907.4775v2 .

[2] Андреас Бласс и Юрий Гуревич. Отношения эквивалентности, инварианты и нормальные формы . SIAM J. Comput. 13: 4 (1984), 24-42.

Вот попытка другого ответа, где мы ослабим требование к «представителю»; на самом деле он не должен быть членом класса эквивалентности, а просто функцией, идентифицирующей класс эквивалентности.

Предположим, у вас есть группа, в которой вы можете проводить тестирование членства в подгруппах. То есть, учитывая , вы можете проверить, находится ли h в подгруппе, порожденной g 1 , … , g k .$g_1, g_2, \ldots, g_k$$h$$g_1, \ldots, g_k$

Пусть ваши классы эквивалентности будут множествами элементов которые порождают одну и ту же подгруппу. Легко проверить, порождают ли два набора одну и ту же подгруппу. Однако не совсем понятно, как вы можете найти уникальный идентификатор для каждой подгруппы. Я подозреваю, что это действительно пример, если вы принимаете группы черного ящика с проверкой членства в подгруппах. Тем не менее, я не знаю, существует ли какая-либо группа, не относящаяся к оракулу, где эта проблема кажется сложной.$g_1, g_2, \ldots, g_k$

Вот надуманный пример. Объектами являются пары $(H,X)$ где $H$ - формула SAT, а $X$ - предполагаемое присвоение переменных. Скажите $(H,X) \sim (H',X')$ если $H=H'$ и либо (a) $X$ и $X'$ оба удовлетворяют назначениям, либо (b) $X$ и $X'$ оба не удовлетворяют назначениям. Это рефлексивно, симметрично и транзитивно. Каждый неудовлетворен$H$ имеет один класс эквивалентности, состоящий из всех$(H,X)$ . Каждый выполнимый$H$ имеет класс всех$(H,X)$ где$X$ - удовлетворяющее присваивание, и другой класс с неудовлетворительными.

Проверка ли $(H,X) \sim (H',X')$ легко , так как мы просто проверить , если $H=H'$ , то если $X$ удовлетворяет $H$ , то , если $X'$ удовлетворяет $H$ . Но для вычисления канонического члена заданного класса $(H,X)$ с $H$ удовлетворяемым $X$кажется слишком сложным (я не уверен, как лучше доказать твердость). Мы можем легко внедрить дополнительное решение для экземпляров SAT, поэтому знание одного решения, как правило, не поможет нам найти другое решение, не говоря уже о выборе канонического. (Редактировать: я имею в виду, что я не ожидаю какого-либо эффективного алгоритма для нахождения дополнительных решений при первом решении. Потому что мы могли бы использовать его для решения проблем SAT, сначала «внедрив» дополнительное решение в проблему, а затем направив его на алгоритм. См. комментарии.)

Это открытый вопрос, по крайней мере, для графиков. Я считаю, что последний прогресс

Бабаи и Кучера, «Каноническая маркировка графиков в линейном среднем времени», ФОКС, 1979

which gives an (expected) linear time algorithm for a canonical graph that is correct with probability $1 - \frac{1}{2^{O(n)}}$

You can read more on Wikipedia. Note that a derandomized version of Babai’s algorithm would mean that no such example exist for graphs.

Testing whether two circuits of size $\leq N$ circuits are equivalent.

To determine if $C_1 \sim C_2$ you only need to evaluate at the $2^n$ input points. To determine a class representative, one would probably have to test all $2^{\Omega(N \log N)}$ possible circuits. For $N$ sufficiently large this is exponentially harder than testing circuit equivalence.

A famous example from descriptive set theory:

Let us define an equivalence relation $\sim$ on $\mathbb R$ by

This is a rather "easy" equivalence relation, in particular it's measurable.

But finding representatives amounts to finding a Vitali set, which requires the Axiom of Choice and cannot be measurable.

Let the objects in your universe be the triples ($\Phi, b, i)$ where $\Phi$ be a Satisfiability problem, on variables $x_0, \ldots, x_{k-1}$, $b$ is either 0 or 1, and $i$ is a bitstring of length $k$, where $\Phi(i)=b$. That is, $i$ is an assignment to $x_0, \ldots, x_k$ that satisfies $\Phi$ if $b$ is 1 or does not satisfy $\Phi$ if $b$ is 0.

Two objects are equivalent if they have the same $\Phi$. Easy to check.

Let the representative object be the lexicographically greatest among all in the equivalence class.

The representative is NP-complete to find: it would solve SAT, since if the lexicographically greatest has $b=0$, then $\Phi$ is unsatisfiable; if it has $b=1$, it is satisfiable.

Seems that most NP-complete problems can be posed this way; it's a matter of placing the certificate of membership into the encoding of the element.

I thought maybe this was a homework problem, which is why I didn't post the solution earlier. I should have done; I could have used those points that @david-eppstien got. Goodness knows, he doesn't need them.

I suppose you can easily achieve that for virtually any problem of the type you describe.

Trivial example: Suppose objects are strings, and any $x$ is equivalent to only itself. Determining whether two elements are equivalent is always easy (it is simply equality). However, you can define $f()$ as your favorite injective hard function.