Pytania oznaczone «graph-isomorphism»

Załóżmy, że i G 2 to dwa niekierowane wykresy na zbiorze wierzchołków { 1 , … , n } . Wykresy są izomorficzne wtedy i tylko wtedy, gdy występuje permutacja Π taka, że G 1 = Π ( G 2 ) lub bardziej formalnie, jeśli istnieje permutacja Π taka, że ( i , j ) jest krawędzią w G 1 wtedy i tylko if ( Π ( i...

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ę

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...

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...

Ł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...

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...

Próbuję zrozumieć związek między izomorfizmem grafu a problemem ukrytej podgrupy. Czy jest na to dobre

Minęło ponad rok od wycofania i korekty w styczniu 2017 r. Czy są jakieś wiadomości? Jeśli nie, czy to normalne, że walidacja trwa tak długo? Spodziewałbym się, że zyska dużo uwagi. Czy ktoś z ważnych osób wypowiedział się, by poprzeć / wątpić w quasi-wielomianowy...

Motywowane komentarzu Fortnow w sprawie mojego postu, dowód, że problemem nie jest izomorfizm grafów -CompleteNPNPNP G I N P N P P G I P , a fakt, że jest głównym kandydatem do -intermediate problemu (nie -Complete ani w ) Jestem zainteresowany znanych dowodów że nie jest w...

Zainspirowany tym pytaniem jest faktoring znany jako P-hard , zastanawiam się, jaki jest obecny podobny stan wiedzy na temat twardości izomorfizmu grafów. Jestem pewien, że obecnie nie wiadomo, czy GI jest w P, ale: jaka jest obecnie największa klasa, w której GI jest trudniejsza? (nie było...

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...

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...

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...

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...

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...

-fixed punkt bezproblemowe automorfizmem prosi wykresu automorfizm, który porusza się co najmniej k ( n ) węzłów. Problem polega na tym, że N P jest kompletne, jeśli k ( n ) = n c dla dowolnego c > 0.kkkk ( n )k(n)k(n)N.P.N.P.NPk(n)=nck(n)=nck(n)=n^cccc Jeśli jednak to problemem jest czas...

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...

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...

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 wiadomo, czy izomorfizm wykres (GI) do silnie graf regularny (SRGs) jest P . Czy są jakieś wskazówki, że może, ale nie musi, być GI -Complete? Czy w takich przypadkach są jakieś poważne konsekwencje? (Podobne do przekonania, że oznaczenie geograficzne może nie być