Pytania otagowane jako graph-isomorphism

Dwa wykresy G, H są izomorficzne, jeśli istnieje znakowanie wierzchołków G, które wytwarza H, i odwrotnie. Graficzny problem izomorfizmu (GI) ma decydować, czy dwa podane są izomorficzne. Oprócz praktycznego zainteresowania, Karp w 1972 r. Stwierdził, że ma nieznaną złożoność, jest jednym z niewielu naturalnych kandydatów na problem pośredni NP i doprowadził do powstania klasy złożoności AM.


3
Konsekwencje quasi-wielomianowego algorytmu czasowego dla problemu izomorfizmu grafowego
Problemem wykres Izomorfizm (Gl) jest prawdopodobnie najbardziej znanym kandydatem na NP pośredniego problemu. Najbardziej znanym algorytmem jest algorytm subwykładniczy z czasem działania . Wiadomo, że GI nie jest -kompletny, chyba że hierarchia wielomianowa się załamie.2O(nlogn√)2O(nlog⁡n)2^{O(\sqrt{n \log n})}NPNP\mathsf{NP} Jakie byłyby teoretyczne konsekwencje złożoności quasi-wielomianowego algorytmu czasowego dla problemu grafowego izomorfizmu? Czy …

3
Techniki pokazujące, że problemem jest twardość „otchłani”
Biorąc pod uwagę nowy problem w którego prawdziwa złożoność jest gdzieś pomiędzy P a ukończeniem NP, istnieją dwie metody, o których wiem, że mogą być wykorzystane do udowodnienia, że ​​rozwiązanie tego jest trudne:N P.N.P.\mathsf{NP}P.P.\mathsf{P} Pokaż, że problem dotyczy GI (GI = Graph Isomorphism) Pokazują, że problem w . Według znanych …

1
Czy można zdecydować o izomorfizmie grafowym za pomocą niedeterminizmu opartego na pierwiastku kwadratowym?
Ograniczonym nondeterminism łączy funkcję z klasy języków akceptowanych przez deterministycznych maszyny Turinga zasobach ograniczona, w celu utworzenia nowej klasy - . Ta klasa składa się z tych języków, które są akceptowane przez jakąś niedeterministyczną maszynę Turinga przestrzegającą tych samych granic zasobów, jakie są używane do zdefiniowania , ale gdzie może …

3
Certyfikat CoNP dla Graph Isomorphism
Łatwo zauważyć, że izomorfizm wykresu (GI) występuje w NP. Poważnym otwartym problemem jest to, czy GI jest w CoNP. Czy są potencjalni kandydaci właściwości grafów, które można wykorzystać jako certyfikaty CoNP dla GI? Jakieś przypuszczenia, które sugerują, że ? Jakie są implikacje ?GI∈coNPGI∈coNPGI \in coNPGI∈coNPGI∈coNPGI \in coNP

1
Odrzucenie dowodu: amatorskie recenzje ambitnych artykułów KR-u
Myślę, że przeczytałem zbyt wiele ambitnych artykułów KR-u . Problem polega na tym, że dokumenty te nie są recenzowane, ale często brzmią interesująco i przechodzą podstawowe kontrole wiarygodności. A może nie, a ja muszę tylko poprawić swoje kontrole wiarygodności. Oto ostatnia próbka takich dokumentów: Drzewa wyjątkowości: możliwe podejście wielomianowe do …





2
„Mały” wykres izomorfizmu
Myśląc o złożoności testowania izomorfizmu wykresów asymetrycznych (patrz moje powiązane pytanie dotyczące cstheory), przyszło mi do głowy pytanie uzupełniające. Załóżmy, że mamy do wielomianu czasu maszynowego Turinga , który na wejściu generuje wykres G M , n z n węzłów.MMM1n1n1^nGM,nGM,nG_{M,n}nnn Możemy zdefiniować problem ΠMΠM\Pi_M : („Małe” GI): Biorąc pod uwagę …

4
Otwarte problemy związane z izomorfizmem grafowym
Obecnie prowadzę przegląd literatury dotyczący problemu izomorfizmu grafowego (GI). Chciałbym poznać kilka otwartych pytań związanych z następującymi zagadnieniami Jakie są parametry wykresu, dla których ustalona zdolność pomiarowa GI jest otwartym problemem. Jakie są parametry wykresu, przez ustalenie ich wielomianowej zdolności do rozwiązywania GI nie jest znana. Złożoność GI, gdy jest …

2
Złożoność problemu przecięcia cosetów
Biorąc pod uwagę grupę symetrii i dwie podgrupy i , czy ?SnSnS_nG,H≤SnG,H≤SnG, H\leq S_nπ∈Snπ∈Sn\pi\in S_nGπ∩H=∅Gπ∩H=∅G\pi\cap H=\emptyset O ile mi wiadomo, problem ten znany jest jako problem przecięcia cosetów. Zastanawiam się, jaka jest złożoność? W szczególności, czy wiadomo, że ten problem występuje w CoAM? Co więcej, jeśli jest ograniczone do abelowego, …

2
Problem z izomorfizmem grafów
Robię przegląd literatury na temat problemu izomorfizmu grafów. Większość artykułów, które czytam, są napisane przez EM Luksa i Laszlo Babai. W tych pracach wykorzystano znajomość teorii grup i teorii złożoności na wysokim poziomie. Ponieważ jestem nowy w tej dziedzinie, wiele rzeczy nie jest dla mnie oczywistych. Czy ktoś może mi …

2
Delikatne wprowadzenie do izomorfizmu grafów dla grafów o ograniczonej wartościowości
Czytam o klasach grafów, dla których izomorfizm grafów ( ) jest . Jednym z takich przypadków są wykresy ograniczonej wartościowości (maksimum nad stopniem każdego wierzchołka), jak wyjaśniono tutaj . Ale uznałem to za zbyt abstrakcyjne. Byłbym wdzięczny, gdyby ktokolwiek mógł zasugerować mi referencje o charakterze ekspozycyjnym. Nie mam silnego doświadczenia …

1
Jak cytować nowy wynik izomorfizmu grafu Babai?
Niedawno Babai opublikował artykuł na temat STOC 2016, twierdząc, że izomorfizm grafów można rozwiązać w czasie quasipolynomialnym. Na początku 2017 r. Babai wycofał roszczenie quasipolomomial z powodu poważnych błędów wykrytych przez Haralda Helfgotta. Jak wyjaśnił sam Babai, ta wada sprawia, że ​​poprawa jest bardziej skromna pod względem czasu działania. Około …

1
Kontrprzykład efektywnego algorytmu Corneila dla izomorfizmu grafów
W pracy „Efficient Al Algorytm for Graph Isomorphism” autorstwa Corneila i Gotlieba, 1970, stwierdzono hipotezę, na której opierał się algorytm rozwiązywania GI w czasie wielomianowym. Mianowicie: że reprezentatywne wykresy wykazują podział automorfizmu na dany wykres Oczywiście, ta hipoteza nie została do tej pory udowodniona (w przeciwnym razie wiedzielibyśmy, że GI …


2
podobne matryce
Biorąc pod uwagę dwa macierzy i , problem decydowania o istnieniu macierzy permutacji takiej, że jest równoważny (Izomorfizm Grafów). Ale jeśli rozluźnimy aby był tylko odwracalną matrycą, to jaka jest złożoność? Czy istnieją jakieś inne ograniczenia dotyczące odwracalnej macierzy , oprócz tego, że są permutacją, które wiążą ten problem z …

1
Twardość NP problemu podziału grafu?
Jestem zainteresowany tym problemem: Biorąc pod uwagę undirected wykres , Czy istnieje podział na wykresach i takie, że i są izomorficzne?G(E,V)G(E,V)G(E, V)GGGG1(E1,V1)G1(E1,V1)G_1(E_1, V_1)G2(E2,V2)G2(E2,V2)G_2(E_2, V_2)G1G1G_1G2G2G_2 Tutaj jest podzielony na dwa rozłączne zestawy i . Zestawy i niekoniecznie są rozłączne. i .EEEE1E1E_1E2E2E_2V1V1V_1V2V2V_2E1∪E2=EE1∪E2=EE1∪E2=EV1∪V2=VV1∪V2=VV1∪V2=V Ten problem jest co najmniej tak trudny jak problem z …


2
Twarde instancje do testowania izomorfizmu grafów
Czy przypadek bardzo regularnych grafów jest najtrudniejszy do testowania GI? gdzie „najtrudniejszy” jest używany w pewnym sensie „zdrowego rozsądku” lub „średnio”, że tak powiem. Wolfram MathWorld wspomina o niektórych „patologicznie trudnych grafach”. Czym oni są? Mój przykładowy zestaw 25 par wykresów: http://funkybee.narod.ru/graphs.htm Testowałem wiele innych, ale wszystkie tego samego rodzaju …




2
Podejścia do GI inspirowane problemem węzłów
Zarówno GI, jak i Knot Problem stanowią problem decydowania o równoważności strukturalnej obiektów matematycznych. Czy są jakieś wyniki ustanawiające powiązania między nimi? Ładne powiązania problemu węzłów z fizyką statystyczną zostały zbadane za pomocą wielomianów węzłów , czy istnieją podobne wyniki dla ?G IsoljaGI Byłoby to szczególnie pomocne, aby wiedzieć, czy …

1
Generowanie wykresów za pomocą trywialnych automorfizmów
Sprawdzam jakiś model kryptograficzny. Aby pokazać jego nieadekwatność, opracowałem wymyślony protokół oparty na izomorfizmie grafowym. Zakładanie istnienia algorytmów BPP zdolnych do generowania „trudnych wystąpień problemu z izomorfizmem grafów” jest „powszechne” (a jednak kontrowersyjne!). (Wraz ze świadkiem izomorfizmu). W moim skonstruowanym protokole założę istnienie takich algorytmów BPP, które spełniają jeden dodatkowy …

2
Czy algorytm quasiipolomialnego czasu Babai faktycznie generuje izomorfizm?
Mam (mam nadzieję, że proste, może głupie) pytanie na przełomowy artykuł Babai, który pokazuje, że jest quasipolynomial.GIGI\mathsf{GI} Babai pokazał, jak stworzyć certyfikat, że dwa wykresy dla są izomorficzne, z czasem quasipolynomial in.i ∈ { 1 , 2 } v = | V i |Gi=(Vi,Ei)Gi=(Vi,Ei)G_i=(V_i,E_i)i∈{1,2}i∈{1,2}i\in\{1,2\}v=|Vi|v=|Vi|v=|V_i| Czy Babai rzeczywiście pokazać , jak …


1
Testowanie izomorfizmu grafów asymetrycznych
Czytając pytanie Przykłady gdzie wyjątkowość rozwiązania sprawia, że łatwiej znaleźć , nowy (? Łatwiej) pytanie przyszło mi do głowy: Właściwie nie wiemy, czy izomorfizm grafów ( ) problem jest w P .GIGIGIPPP Ale co się stanie, jeśli założymy, że zarówno i G 2 są asymetryczne (tj. Oba mają jedynie trywialny …

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.