Является ли случай строго регулярных графов самым сложным для тестирования ЖКТ? где «самый трудный» используется в некотором смысле «здравый смысл», или, так сказать, «в среднем». Wolfram MathWorld упоминает некоторые «патологически сложные графы». Кто они такие? Мой примерный набор из 25 пар...
-fixed точки без проблем автоморфизма запрашивает автоморфизм графа , который перемещается по крайней мере , к ( п ) узлы. Проблема в том, что N P- полна, если k ( n ) = n c для любого c > 0.kkkk(n)k(n)k(n)NPNPNPk(n)=nck(n)=nck(n)=n^cccc Однако, если то задача полиномиального времени Тьюринга...
Рассмотрим следующую проблему: учитывая граф запросов G=(V,E)G=(V,E)G = (V, E) и опорный граф , мы хотим найти инъективное отображение которое минимизирует количество ребра такие, что . Это обобщение проблемы изоморфизма подграфа, где мы позволяем подграфам быть изоморфными вплоть до нескольких...
1-тусклый алгоритм Вейсфейлер-Леман (WL) широко известен как каноническая маркировка или алгоритм , цвета уточнения. Это работает следующим образом: Начальная раскраска равномерна, C 0 ( v ) = 1 для всех вершин v ∈ V ( G ) ∪ V ( H ) .С0С0C_0С0( v ) = 1С0(v)знак равно1C_0(v) = 1v ∈ V( G ) ∪ V(...
Граф Изоморфизм ( ) является хорошим кандидатом для N P -проблемой задачи. N P -intermediate проблемы существуют , если Р не = Н Р . Я ищу естественную проблему, которая трудна для G I при редукции Карпа (графовая задача X такая, что G I < m p X...
GI и проблема узлов являются проблемой определения структурной эквивалентности математических объектов. Есть ли какие-либо результаты установления связей между ними? Хорошие связи проблемы узлов со статистической физикой были изучены с помощью полиномов узлов , есть ли похожие результаты для ?G...
Я пересматриваю некоторую криптографическую модель. Чтобы показать его неадекватность, я разработал искусственный протокол, основанный на изоморфизме графа. Это «обычное дело» (еще спорный!) Предположить существование BPP алгоритмов способны генерировать «жесткие экземпляры проблемы Изоморфизма...
Для группы перестановок на и двух векторов где - конечный алфавит, который здесь не совсем уместен, вопрос есть ли какой-нибудь такой, что где означает применение перестановки к ожидаемым образом.GGG[n]={1,⋯,n}[n]={1,⋯,n}[n]=\{1, \cdots, n\}u,v∈Γnu,v∈Γnu,v\in \Gamma^nΓΓ\Gammaπ∈Gπ∈G\pi\in...
У меня есть (надеюсь, простой, возможно, глупый) вопрос об исторической работе Бабая, показывающей, что является квазиполиномиальным.G Iграммя\mathsf{GI} Бабай показал, как получить сертификат, что два графа для i ∈ { 1 , 2 } изоморфны по времени, квазиполиномиальны по v = | V я | ,граммя= ( Vя,...
При чтении вопрос примеров , где единственность решения делает его легче найти , новый (? Проще) возник вопрос , на мой взгляд: на самом деле мы не знаем , если Изоморфизм графов ( проблема) в .GIGIGIPPP Но что произойдет, если мы предположим, что обаG1G1G_1 и асимметричны (т.е. оба имеют только...
Я хочу быть очень конкретным. Кто-нибудь знает опровержение или доказательство следующего предложения: ∃p∈Z[x],n,k,C∈N,∃p∈Z[x],n,k,C∈N,\exists p \in \mathbb{Z}[x], n, k, C \in \mathbb{N}, ∀G,H∈STRUC[Σgraph](min(|G|,|H|)=n,G≄H),∀G,H∈STRUC[Σgraph](min(|G|,|H|)=n,G≄H),\forall G, H \in...
Какие еще языки проблем, отличные от изоморфизма графов, есть в ? Можете ли вы дать некоторые ссылки?Nп∩ c o A MNP∩coAMNP\cap coAM Обновление: Я забыл упомянуть , что я заинтересован в языках , не известно, в .c o...
Представьте, что у нас есть два размера mmm наборов точек X,Y⊂RnX,Y⊂RnX,Y\subset \mathbb{R}^n . Какова (временная) сложность тестирования, если они отличаются только ротацией? : существует матрица вращения OOT=OTO=IOOT=OTO=IOO^T=O^TO=I такая, что X=OYX=OYX=OY ? Здесь возникает проблема...
В известном контрпримере для изоморфизма графа с помощью метода Вейсфейлера-Лемана (WL) в этой статье Кай, Фюрер и Иммерман построили следующий гаджет . Они строят граф определяемый какXk=(Vk,Ek)Xk=(Vk,Ek)X_k = (V_k, E_k) Vk=Ak∪Bk∪Mk where Ak={ai∣1≤i≤k},Bk={bi∣1≤i≤k}, and Mk={mS∣S⊆{1,2,…,k}, |S| is...
Были предприняты некоторые попытки решить проблему изоморфизма графов с помощью квантового случайного блуждания жестких бозонов (симметричное, но без двойного заполнения). Симметричная степень матрицы смежности, которая казалась многообещающей, оказалась неполной для общих графов в этой статье...
Я заинтересован в изучении полных задач Изоморфизма графов (GI). В работе Kellogg S. Booth (1979) «Проблемы, полиномиально эквивалентные изоморфизму графа» доказано, что многие базовые задачи являются GI-полными с использованием методов замены краев, методов композиции и т. Д. Я хотел бы изучить...
Часть трудностей, связанных с поиском дополнительной информации об этой проблеме, заключается в том, что проблема сопоставления графов отличается от ее гораздо более известного кузена, проблемы сопоставления, но ее трудно отличить от нее при использовании поисковых систем. Даны два графа и такие,...
Я хотел бы спросить, есть ли уже опубликованный результат по этому вопросу: Мы берем все возможные разные пути между каждой парой узлов двух соединенных регулярных (со степенью , скажем, числом узлов ) графов и записываем их длины. Конечно, это число различных путей является экспоненциальным. Мой...
Для любого простого неориентированного графа G нетривиально определить, имеет ли G нетривиальные (неединичные) автоморфизмы. Но каковы результаты на верхних / нижних границах этой проблемы...
Является ли проблема конечного обратного полугруппового изоморфизма GI-полной ? Здесь конечные обратные полугруппы предполагаются заданными их таблицами...