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