Вопросы с тегом «gr.group-theory»

42
Приложения теории представлений симметрической группы

Вдохновленный этим вопросом и, в частности, последним абзацем ответа Ор, у меня есть следующий вопрос: Знаете ли вы какие-либо приложения теории представлений симметрической группы в TCS? Симметрическая группа SNSnS_n является группой всех перестановок { 1 , … , n }{1,…,n}\{1, \ldots, n\} с...

18
Можно ли проверить, является ли вычислимое число рациональным или целым?

Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...

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

При условии, что группа симметрии и две подгруппы и , имеет ли место ?SnSnS_nG,H≤SnG,H≤SnG, H\leq S_nπ∈Snπ∈Sn\pi\in S_nGπ∩H=∅Gπ∩H=∅G\pi\cap H=\emptyset Насколько я знаю, эта проблема известна как проблема пересечения смежных классов. Мне интересно, в чем сложность? В частности, известна ли эта...

16
Сложность распознавания вершинно-транзитивных графов

Я не обладаю знаниями в области теории сложности с участием групп, поэтому я прошу прощения, если это хорошо известный результат. Вопрос 1. Пусть - простой неориентированный граф порядка n . Какова вычислительная сложность (с точки зрения n ) определения, если GGGGnnnnnnGGG вершинно-транзитивным?...

14
Существуют ли группы с проблемами слов в произвольных P-степенях?

Давно известно, что при любой степени восстановления существует конечно представленная группа, проблема слова в которой есть в этой степени. У меня вопрос: верно ли то же самое для произвольных полиномиальных степеней Тьюринга? В частности, существует ли разрешимое множество , существует ли конечно...

14
Существуют ли высокосимметричные NP- или P-полные языки?

Существует ли , NP- или P-полный язык, имеющий некоторое семейство групп симметрии (или группоид , но тогда алгоритмические вопросы становятся более открытыми), действующий (за полиномиальное время) на множествах такой, что орбит мало, т. е. такой, что для достаточно больших и некоторого c , и...

13
Гауссово исключение с точки зрения группового действия

Гауссовское исключение делает определитель матрицы полиномиальным временем вычислимым. Снижение сложности в вычислении детерминанта, которое в противном случае является суммой экспоненциальных членов, обусловлено наличием альтернативных отрицательных признаков (отсутствие которых делает вычисление...

12
Сложность членства-тестирования для конечных абелевых групп

Рассмотрим следующую задачу проверки принадлежности к абелевой подгруппе . Входы: Конечная абелева группа с произвольно большим .G = Zd1× Zd1… × ZdмG=Zd1×Zd1…×ZdmG=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}dяdid_i Производящая-набор { ч1, ... , чN}{h1,…,hn}\lbrace...

12
Книга для самостоятельного изучения алгоритмов в теории групп

Я интересуюсь математикой на TCS. Я хочу самостоятельно изучить алгоритмы и их сложность для решения групповых теоретических задач, таких как поиск порядка элементов, перечисление смежных классов, поиск генератора, проверка, генерирует ли данное подмножество группу. Какую книгу я должен...

11
Определение того, что может быть достигнуто путем перестановки элементов некоммутативной группы

Зафиксируем конечную группу . Меня интересует следующая проблема решения: входными данными являются некоторые элементы группы с частичным порядком на них, и вопрос заключается в том, существует ли перестановка элементов, которая удовлетворяет порядку и такова, что композиция элементов в этом...

11
Трудность в понимании квантового алгоритма для задачи об абелевой скрытой подгруппе

У меня есть трудности в понимании последних шагов алгоритма AHSP. Пусть абелева группа и е функция , которая скрывает подгруппу H . Пусть G * представляет двойную группу G .GGGfffHHHG∗G∗G^*GGG Вот шаги алгоритма Сначала подготовь государство, .I=1|G|∑g∈G|g⟩|0⟩I=1|G|∑g∈G|g⟩|0⟩\qquad \displaystyle...

11
Какой самый сложный пример для проблемы группового изоморфизма?

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

10
Недавний прогресс в алгоритмах групп перестановок?

Меня интересуют алгоритмы для конечных групп, реализованные в пакете GAP. Кажется, что все известные алгоритмы в этой области имеют дело с группами перестановок / матричными группами; Двумя фундаментальными являются Schreier-Sims [1970] и Butler [1979], см., например, «Алгоритмы для групп...

10
Кодирование наборов перестановок с помощью генерирующего набора и набора исключенных элементов

Известны алгоритмы полиномиального времени для нахождения порождающих множеств групп перестановок, что интересно, поскольку мы можем затем представить эти группы кратко, не отказываясь от алгоритмов полиномиального времени для ответа на многие интересные вопросы, связанные с этими группами. Однако...

10
Диаметр графов Кэли подгрупп в

Бабай и Сэресс доказали, что при наличии подгруппы и порождающего множества в любая перестановка в может быть записана как произведение образующих и их обратных длины . Эта граница является оптимальной, поскольку имеет элемент порядка . S G G e ( 1 + o ( 1 ) ) √G ≤ SNG≤SnG \leq S_nSSSгGGгGG...

10
Является ли этот многогранник «упаковки подгрупп» интегральным?

Пусть - конечная абелева группа, а - многогранник в определенный как точки удовлетворяющие следующим неравенствам:P R Γ xΓΓ\GammaппPрΓрΓ\mathbb{R}^\GammaИксИксx Σг∈ GИксг≤ | G |Иксг≥ 0∀ G ≤ Γ∀ г∈ ΓΣг∈гИксг≤|г|∀г≤ΓИксг≥0∀г∈Γ\begin{array}{cl} \sum_{g\in G} x_g \le |G| & \forall G \le \Gamma \\ x_g...

9
Число автоморфизмов графа для графа изоморфизма

Позволять GGG а также HHH быть двумя rrrрегулярные связные графы размера nnn, ПозволятьAAA быть набором перестановок PPP такой, что PGP−1=HPGP−1=HPGP^{-1}=H, ЕслиG=HG=HG=H тогда AAA это множество автоморфизмов GGG, Каков самый известный верхний предел размера AAA? Есть ли какие-либо результаты для...

9
Сложность вычисления лексикографически минимального элемента орбиты

Учитывая сильные генераторы для группы ( G ≤SN, * )(G≤Sn,∗)(G \leq S_n, *) действуя на нити длины Nnn и элемент s ∈ { 0 , 1}Ns∈{0,1}ns \in \{0, 1\}^nНасколько сложно вычислить лексикографически минимальный элемент G . sG.sG.sорбита sss в гGG?...

9
Есть ли кандидат на постквантовое одностороннее групповое действие?

Существует ли известное семейство групповых действий с назначенным элементом в наборе, над которым выполняется действие, где известно, как эффективно \: выборка (по существу, равномерно) из групп, вычисление обратных операций, вычисление групповых операций и вычисление групповых действий \: и нет...