Czy problem izomorfizmu grafu został rozwiązany?

13

Wydaje się, że strona problemu z izomorfizmem grafu w Wikipedii wskazuje, że nie, nie została rozwiązana. Jednak mój przyjaciel zwrócił uwagę na algorytm wielomianu czasowego dla izomorfizmu grafowego . Nie jestem wystarczająco wyrafinowany, aby podążać za rozumowaniem zawartym w artykule.

Mam własną bardzo trudną próbę zastosowania algorytmu wielomianowego bez żadnego dowodu, ale chciałbym wiedzieć, czy ten problem został rozwiązany przed kontynuowaniem.

Czy problem izomorfizmu wykresu został rozwiązany?

complexity-theory reference-request time-complexity graph-isomorphism Tyler Spaeth
źródło
1
warte pytania. W przypadku recenzji cybernetycznych byłoby lepiej, gdyby respondenci / odpowiedzi wskazywali konkretny błąd (błędy) w pracy, a nie informacje ogólne. co prawda zastrzeżenie jednak tutaj jest to, co zawodowi naukowcy uważają tego rodzaju działań. arxiv jest pełen błędnych dokumentów, wiele na temat P kontra NP, ale wiele innych półsławnych problemów przyciąga amatorskie wysiłki, np. także hipoteza Collatza, bliźniacze liczby pierwsze, hipoteza Goldbacha itp.
dniu
7
@vzn Nie sądzę, aby marnowanie czasu na czytanie dokumentów, które są prawie na pewno nieprawidłowe i nie rzucały nowego światła na problem, nie ma sensu.
Yuval Filmus
2
@vzn Nie rozumiem twojej skargi. Odpowiedź DW (opublikowana na godzinę przed komentarzem) prowadzi do komentarza, który wskazuje na konkretny błąd w omawianej pracy ArXiv.
David Richerby,
2
@vzn Papier ArXiv zawiera błąd. Ten błąd nie został poprawiony. Nie ma potrzeby przeprowadzania dodatkowej oceny. Nie mam pojęcia, co mówisz, z drugiej ręki: kontrprzykład jest kontrprzykładem, niezależnie od tego, czy został ci przekazany przez jego odkrywcę, czy przez dilera narkotyków, który kręci się za tym podejrzanym barem Autostrada.
David Richerby,
1
@vzn Prawdopodobnie nie został poprawiony, ponieważ autor nie mógł naprawić błędu. Pamiętaj, że ArXiv nie zezwala na wycofywanie manuskryptów, nawet jeśli okażą się one nieprawidłowe.
David Richerby,

Odpowiedzi:

23

Nie. Ten papier wydaje się być wadliwy. Błąd został wyjaśniony w komentarzu Tracy Hall na temat MathOverflow . Kolejny komentarz twierdzi, że autor później zdał sobie sprawę, że jego algorytm ma wadę.

Jak wyjaśnia Yuval, często zdarza się, że amatorzy próbują rozwiązać te problemy; mają skłonność do wad. Jeśli chodzi o wyniki znanych słynnych problemów (np. P vs NP, izomorfizm wykresów itp.), Polecam poszukać publikacji w renomowanych recenzowanych konferencjach i czasopismach - recenzowanie nie jest idealne, ale artykuły recenzowane mają znacznie większe prawdopodobieństwo bycia poprawnym.

DW
źródło
17

Nie, problem izomorfizmu grafu nie został rozwiązany. Artykuł, do którego linkujesz, pochodzi z lat 2007–2008 i nie został zaakceptowany przez szerszą społeczność naukową. (Gdyby tak było, wiedziałbym o tym.)

Wykres izomorfizm, podobnie jak wiele innych znanych problemów, przyciąga wiele prób amatorów. Prawie zawsze się mylą. Odradzałbym próbowanie rozwiązania tego problemu bez uprzedniej znajomości matematyki na poziomie badawczym.

Yuval Filmus
źródło
2
innym sposobem radzenia sobie z tego rodzaju roszczeniami ekspertów jest niemożność lub bariera. następnie bardziej pouczające obalenie ma postać „w artykule zastosowano argument [x] w celu rozwiązania problemu izomorfizmu, ale z badań [a, b, c] wiadomo, że istnieje specyficzna bariera dla tego typu podejścia, a artykuł wydaje się nieświadomy tej bariery lub ujawnia konkretnie, w jaki sposób można ją pokonać. ” znane są wyniki dotyczące problemu izomorfizmu i innych kluczowych problemów, np. P vs NP.
vzn
1
Podejmowanie takich nierozwiązanych problemów (i porażka ...) może być bardzo owocnym ćwiczeniem edukacyjnym, jeśli przyjdzie się we właściwy sposób.
Nick Alger,
jednak pewne spory : dowody / twierdzenia mają w pewnym stopniu ważność niezależną od „akceptacji przez szerszą społeczność naukową” i wiedzy o nich przez poszczególne osoby. np. gdy pierwszy dowód zostanie wprowadzony po raz pierwszy, nie jest on natychmiast / natychmiast „akceptowany” przez kogokolwiek innego niż autor. dalsze wsparcie dla tej dynamiki można znaleźć w historii matematyki. a czasami długie okresy mogą
upłynąć
8

Byłbym bardzo wątpliwy, że tak jest (w sensie dowodu na istnienie algorytmu wielomianowego czasu). Chociaż nie jest niemożliwe, aby papier był poprawny, istnieje wiele znaków ostrzegawczych:

  1. Autor nie opublikował wyniku w recenzowanym miejscu (nawet po 7 latach).
  2. Wydaje się, że autor nigdzie nie opublikował niczego innego.
  3. Artykuł przedstawia algorytmy, ale twierdzenie o poprawności jest nieformalnym argumentem o złożoności.
  4. Dla problemu, który oparł się próbom bardzo sprytnych ludzi, matematyka w gazecie jest zbyt prosta.
  5. Autor nie wydaje się być związany z instytucją akademicką. Wyjaśnia to nowa wersja artykułu.

Ponownie, bez zidentyfikowania wady przez kogoś, nie są to głupie dowody. Być może autor miał unikalny błysk wglądu, a następnie przeszedł do zupełnie innego życia, ale ciężar prawdopodobieństwa jest temu przeciwny - nadzwyczajne roszczenia wymagają nadzwyczajnych dowodów.

Aby rozwinąć (4) ostatnie wiadomości, László Babai stwierdził ostatnio znaczną poprawę znanego algorytmu izomorfizmu grafowego (jeszcze nie ma przedruku, ale można tu znaleźć przyzwoity komentarz na temat jego publicznego wykładu ), dając algorytm pseudo-wielomianowy. Babai i jego koledzy są zdecydowanie bardzo inteligentnymi ludźmi, a matematyka zastosowana do uzyskania tego wyniku jest trudna, głęboka i obejmuje teorię grafów i teorię grup. Biorąc pod uwagę wagę prawdopodobieństwa, jest to oczekiwany poziom znacznego postępu w przypadku takiego problemu.

Luke Mathieson
źródło
3
Punkty 1-4 są mocne, ale 5 jest znacznie bardziej poszlakowych.
David Richerby
(5) jest niepoprawny. instytucja (podobno) jest Technical University of Berlin , a część jest stan sponsorowanych. (1) wspierane przez ten link / przeszukiwacz papieru. artykuł jest cytowany na stronie roszczeń Woegingera .
vzn
3
Babai wycofał roszczenie dotyczące quasipolynomial runtime . Najwyraźniej w analizie wystąpił błąd.
Raphael
roszczenie
quasipolynomial
3

Laszlo Babai twierdził, że znalazł quasipolynomialne rozwiązanie problemu izomorfizmu grafów od 11 listopada 2015 r.

... i wycofał roszczenie wczoraj (4/1/2017):

Źródło: http://jeremykun.com/2015/11/12/a-quasipolynomial-time-alameterm-for-graph-isomorphism-the-details/

bharv14
źródło
Z podanego linku: Babai nie wydał jeszcze przedruku, a kiedy go zapytałem, powiedział „wkrótce, wkrótce”. Dopóki.
scaaahu
Pytanie nie definiuje, co oznaczałoby, że problem z izomorfizmem grafowym liczy się jako rozwiązany, ale najbardziej prawdopodobna interpretacja jest taka: że ktoś znalazł dla niego algorytm wielomianowy lub dał dowód, że nie istnieje taki algorytm wielomianowy . Zgodnie z tą interpretacją odpowiedź ta nie odpowiada na pytanie.
DW
4
Babai wycofał roszczenie dotyczące quasipolynomial runtime . Najwyraźniej w analizie wystąpił błąd.
Raphael
roszczenie
quasipolynomial