Czy Norbert Blum w 2017 roku jest dowodem na to, że poprawny?

Norbert Blum opublikował niedawno 38-stronicowy dowód, że . Czy to jest poprawne?$P \ne NP$

Także na temat: gdzie jeszcze (w Internecie) omawia się jego poprawność?

Uwaga: zakres tego tekstu pytania zmienił się z czasem. Szczegóły znajdują się w komentarzach do pytań.

Jak zauważono tutaj wcześniej, przykład Tardosa wyraźnie obala dowód; daje funkcję monotoniczną, która jest zgodna z CLIQUE dla T0 i T1, ale która leży w P. Nie byłoby to możliwe, gdyby dowód był poprawny, ponieważ dowód dotyczy również tego przypadku. Czy jednak możemy wskazać błąd? Oto, z postu na blogu Liptona, to, co wydaje się być miejscem, w którym dowód się nie udaje:

Pojedynczy błąd stanowi jeden subtelny punkt w dowodzie Twierdzenia 6, mianowicie w kroku 1 na stronie 31 (a także 33, gdzie omawiany jest przypadek podwójny) - pozornie oczywiste twierdzenie, że zawiera wszystkie odpowiednie klauzule zawarte w itp. Wydaje się błędny. C N F ′ ( g $C'_g$$CNF'(g)$

Aby wyjaśnić to bardziej szczegółowo, musimy przejść do metody dowodu i aproksymacji Berga i Ulfberga, która potwierdza oryginalny dowód Razborowa na wykładniczą złożoność monotoniczną dla CLIQUE pod względem przełączników DNF / CNF. Tak to widzę:

Do każdego węzła / bramki obwodu logicznego (zawierającego tylko binarne bramki OR / AND), postać normalna , dwuzłączna postać normalna oraz aproksymatory i są przywiązany. i są po prostu odpowiednimi rozłącznymi i łączącymi normalnymi formami wyjścia bramki. i są również formami rozłącznymi i , ale niektórych innych funkcji, „przybliżających” wyjście bramki. Wymagane są jednak ograniczenia liczby zmiennych w każdym monomialnym dlaβ C N F ( g ) D N F ( g ) C k g D r g C N F D N F D r g C k g D r g C k $g$$\beta$$CNF(g)$$DNF(g)$$C^k_g$$D^r_g$$CNF$$DNF$$D^r_g$$C^k_g$$D^r_g$(mniej niż stała r) oraz w każdej klauzuli dla (mniej niż stała k).$C^k_g$

Przy takim przybliżeniu pojawia się pojęcie „błędu”. Jak obliczany jest ten błąd? Interesuje nas tylko pewien zestaw T0 wejść, na których nasza funkcja całkowita przyjmuje wartość 0, i T1 wejść, na których nasza funkcja całkowita przyjmuje wartość 1 („obietnica”). Teraz przy każdej bramce patrzymy tylko na te dane wejściowe z T0 i T1, które są poprawnie obliczone (zarówno przez i , które reprezentują tę samą funkcję - wyjście bramki w ) na wyjściu bramki i sprawdź, ile błędów / błędów występuje dla iC N F ( g ) g β C k g D r g C k g D r g C k g C k g D r $DNF(g)$$CNF(g)$$g$$\beta$$C^k_g$$D^r_g$w porównaniu z tym. Jeśli bramka jest koniunkcją, wówczas wyjście bramki może poprawnie obliczyć więcej danych wejściowych z T0 (ale poprawnie obliczone dane wejściowe z T1 są prawdopodobnie zmniejszone). Dla , który jest zdefiniowany jako prosta koniunkcja, nie ma jednak nowych błędów na wszystkich tych wejściach. Teraz jest zdefiniowane jako przełącznik CNF / DNF w , więc może być wiele nowych błędów na T0, pochodzących z tego przełącznika. Również na T1 nie ma żadnych nowych błędów na - każdy błąd musi być obecny na każdym z wejść bramki, i podobnie na przełącznik nie wprowadza nowych błędów na T1. Analiza dla bramki OR jest podwójna.$C^k_g$$D^r_g$$C^k_g$$C^k_g$$D^r_g$

Tak więc liczba błędów dla końcowych aproksymatorów jest ograniczona liczbą bramek w , pomnożoną przez maksymalną możliwą liczbę błędów wprowadzonych przez przełącznik CNF / DNF (dla T0) lub przełącznik DNF / CNF (dla T1). Ale całkowita liczba błędów musi być „duża” w co najmniej jednym przypadku (T0 lub T1), ponieważ jest to właściwość pozytywnych spójnych form normalnych z klauzulami ograniczonymi przez , co było kluczowym wglądem w oryginalny dowód Razborova (Lemma 5 w pracy Bluma).$\beta$$k$

Co więc zrobił Blum, aby poradzić sobie z negacjami (które są spychane do poziomu danych wejściowych, więc obwód nadal zawiera tylko binarne bramki OR / AND)?$\beta$

Jego pomysłem jest restrykcyjne przełączanie przełączników CNF / DNF i DNF / CNF, tylko gdy wszystkie zmienne są dodatnie. Wtedy przełączniki działałyby DOKŁADNIE tak, jak w przypadku Berga i Ulfberga, wprowadzając taką samą liczbę błędów. Okazuje się, że jest to jedyny przypadek, który należy wziąć pod uwagę.

Podąża więc za Bergiem i Ulfbergiem, z kilkoma wyróżnieniami. Zamiast dołączać , , i do każdej bramki obwodu , dołącza swoje modyfikacje, , , i , tj. „zredukowane” normalne formy rozłączne i , które według niego różnią się od iD N F ( g ) C k g D r g g β C N N F ' ( g ) D N F ' ( g ) C ′ k g D ' r g C N F ( g ) D N F ( g ) C ' r g D ' $CNF(g)$$DNF(g)$$C^k_g$$D^r_g$$g$$\beta$$CNF'(g)$$DNF'(g)$${C'}^k_g$${D'}^r_g$$CNF(g)$$DNF(g)$„regułą absorpcji”, usuwając zanegowane zmienne ze wszystkich mieszanych monomialów / klauzul (używa on również w tym celu operacji oznaczonej przez R, usuwając całkowicie niektóre monomialy / klauzule; jak już mówiliśmy wcześniej, jego nieco nieformalna definicja R nie jest tak naprawdę problemem , R można sprecyzować, aby było stosowane do każdej bramki, ale to, co jest usuwane, zależy nie tylko od dwóch poprzednich wejść, ale od całego obwodu prowadzącego do tej bramki) i ich aproksymatorów i , który również wprowadził.${C'}^r_g$${D'}^r_g$

Stwierdza on w Twierdzeniu 5, że dla funkcji monotonicznej zredukowane i naprawdę obliczą 1 i 0 na zbiorach T1 i T0 w węźle głównym (którego wyjście jest wyjściem całej funkcji w ). To twierdzenie jest, jak sądzę, poprawne. D N F ′ g 0$CNF'$$DNF'$$g_0$$\beta$

Teraz przychodzi zliczanie błędów. Uważam, że błędy w każdym węźle powinny być obliczane przez porównanie zredukowanego i (które obecnie są prawdopodobnie dwiema różnymi funkcjami), do i jak je zdefiniował. Definicje aproksymatorów papuzie definicje i (krok 1) podczas mieszania zmiennych z negacjami, ale gdy ma do czynienia ze zmiennymi dodatnimi, używa przełącznika jak w przypadku Berga i Ulfberga (krok 2). I rzeczywiście, w kroku 2 wprowadzi taką samą liczbę możliwych błędów jak poprzednio (jest to ten sam przełącznik, a wszystkie zaangażowane zmienne są dodatnie).D N F ' ( g ) C ' r g D ' k g C N F ' D N F $CNF'(g)$$DNF'(g)$${C'}^r_g$${D'}^k_g$$CNF'$$DNF'$

Ale dowód jest błędny w kroku 1. Myślę, że Blum myli , , które naprawdę pochodzą, tak jak je zdefiniował, z poprzednich aproksymatorów (dla bramek , ), z dodatnimi częściami i . Istnieje różnica, dlatego stwierdzenie „ zawiera nadal wszystkie klauzule zawarte w przed przybliżeniem bramki g, które używają klauzuli w lub ” wydaje się być ogólnie źle.γ 2 h 1 h 2 C N F ′ β ( h 1 ) C N F ′ β ( h 2 ) C ′ g C N F ′ β ( g ) γ ′ 1 γ ′ $\gamma_1$$\gamma_2$$h_1$$h_2$$CNF'_\beta(h_1)$$CNF'_\beta(h_2)$$C_g'$$CNF'_\beta(g)$$\gamma_1'$$\gamma_2'$

Znam Aleksandra Razborowa, którego poprzednia praca jest niezwykle ważna i służy jako podstawa dowodu Bluma. Miałem szczęście spotkać się z nim dzisiaj i nie traciłem czasu, prosząc o opinię na temat całej tej sprawy, tego, czy w ogóle widział dowód, czy też nie, i jakie są jego myśli na ten temat, jeśli to zrobi.

Ku mojemu zdziwieniu odpowiedział, że rzeczywiście był świadkiem artykułu Bluma, ale początkowo nie chciał go przeczytać. Ale kiedy otrzymano większą sławę, miał okazję go przeczytać i natychmiast wykrył wadę: mianowicie, że rozumowania podane przez Berga i Ulfberga doskonale pasują do funkcji Tardos, a ponieważ tak jest, dowód Bluma jest koniecznie niepoprawny, ponieważ jest sprzeczny z rdzeniem Twierdzenia 6 w jego pracy.

Zostało to opublikowane jako odpowiedź społeczności, ponieważ (a) to nie moje własne słowa, ale cytat Lucy Trevisan na platformie mediów społecznościowych lub innych osób bez konta CSTheory.SE; oraz (b) każdy powinien zaktualizować to, aktualizując odpowiednie informacje.

Cytując Lucę Trevisan z publicznego postu na Facebooku (14.08.2017), odpowiadając na pytanie dotyczące tego artykułu zadane przez Shachara Lovetta :

Funkcja Andreeva, która, jak się twierdzi, ma złożoność obwodu wielobiegunowego (streszczenie, następnie rozdział 7), jest po prostu jednoczynnikową interpolacją wielomianową w polu skończonym, która, jeśli czegoś mi nie brakuje, można rozwiązać przez eliminację Gaussa

W rzeczywistości nie jest to koniecznie punkt, w którym dowód zawodzi; Następnie Luca udzielił odpowiedzi (15.08.2017), po pytaniu związanym z komentarzem Andrew poniżej:

Masz rację, chłopaki, źle zrozumiałem definicję funkcji Andreeva: nie jest jasne, czy sprowadza się ona do interpolacji wielomianowej

Karl Wimmer skomentował kwestię podniesioną przez Gustava Nordha (powieloną za zgodą Karla):

Aby dodać do tego, nie rozumiem, dlaczego z dwóch pierwszych akapitów dowodu Twierdzenia 5 możemy wnioskować, że oblicza . Widzę tylko pewien rodzaj jednostronności, że oblicza funkcję taką, że implikuje, że ta funkcja to również 1.f D N F ' ( g 0 ) f = $\mathrm{DNF'}(g_0)$$f$$\mathrm{DNF'}(g_0)$$f = 1$

Trzeci akapit też mi nie pomaga: na pewno i jego przełącznik DNF / CNF obliczają tę samą funkcję, ale nie wynika natychmiast, że przełącznik DNF / CNF oblicza (ponieważ może nie), więc nie możemy wyciągać żadnych wniosków na temat klauzul .f D N F ' ( g 0 ) $\mathrm{DNF'}(g_0)$$f$$\mathrm{DNF'}(g_0)$$f$

(Na bok: ta jednostronność jest zgodna z powyższym przykładem Gustava .)

Z innego punktu widzenia z pewnością standardowa sieć obliczająca funkcję monotoniczną może obliczyć funkcje niemonotoniczne w węzłach wewnętrznych. Twierdzenie 5 nie dotyczy funkcji niemonotonowych, więc może nie poprawnie obliczyć podfunkcji w sieci, której węzłem wyjściowym jest (co stanie się w przypadku wielu funkcji niemonotonowych). Z tego powodu nie jestem przekonany, że ta indukcyjna konstrukcja koniecznie będzie ostatecznie poprawna.g D N F ' ( g 0$\mathrm{DNF'}(g)$$g$$\mathrm{DNF'}(g_0)$

Jeśli jestem tu całkowicie poza bazą, daj mi znać!

Od anonimowego użytkownika w reakcji na punkt Karla:

DNF 'i CNF' są po prostu DNF i CNF dla f, w których dokonuje się anulowania literałów przeciwnych, a tym samym redukują je do krótszej postaci. Jest to również wyjaśnione w artykule i jest nieco kłopotliwe z definicji, ale takie właśnie jest. Twierdzenie 5 nie jest problemem, mięso jest w twierdzeniu 6.

I odpowiedź Karla (którą tutaj powtarzam):

Widzę, co mówi anon (dzięki!); mój komentarz nie rozwiązał mojego zamieszania. Jeśli jest monotoniczny i obliczony przy , dobrze jest wziąć , zastosować absorpcję i operator , a wynikowy reprezentuje . Korzystając z tej „jednorazowej” konstrukcji, Twierdzenie 5 jest w porządku - do Twierdzenia 6. Przesunąłem nad tą definicją$f$$g_0$$\mathrm{DNF}(g_0)$$R$$\mathrm{DNF'}(g_0)$$f$$\mathrm{DNF'}(g_0)$

Co nie widzę dlaczego brama brama po zastosowanie absorpcji-and- -as-you-go budowę na stronach 27-28 robi to samo. Wydaje się to konieczne do działania analizy „bramka za bramą” w Twierdzeniu 6, chyba że uwzględniono błąd z tej konstrukcji. To znaczy, nie każda funkcja może nawet być reprezentowane przez DNF z warunkami z tylko literałach spoza zanegowany albo negowany, ale dla każdego węzła , ma zawsze ten kształt. Co jeśli w mojej sieci jest węzeł taki że nie ma takiej reprezentacji?$R$$\mathrm{DNF'}(g_0)$$g$$\mathrm{DNF'}(g)$$g$$\mathrm{res}(g)$

(Kolejny mały (?) Punkt: nie widzę, co robi w konstrukcji „bramka za bramą”; w 1.-4 wydaje się, że jest już standardową konstrukcją DNF, ale z zastosowaną absorpcją i )$R$$\alpha$$R$

(odpowiedź anona) Zgadzam się, że niejasność w definicji R może stanowić problem w sekcji 6. R nie jest wyraźnie zdefiniowane i chyba że jego działanie zależy w jakiś sposób od całego DNF (a nie od wartości DNF 'na bramkach indukcyjnie) , może występować problem. Dowód Deolalikara miał podobny problem - dwie różne definicje były mylone. Tutaj przynajmniej wiemy, co należy rozumieć jako DNF ', a jeśli jest to źródłem problemu w sekcji 6, można łatwo go wyśledzić. Nie wszedłem jednak do sekcji 6, wymaga to zrozumienia dowodów przez aproksymatory Berga i Ulfberga opisanych w sekcji 4, ostatecznie związanych z konstrukcją Razborova z 1985 roku, co nie jest łatwe.

Wyjaśnienie, jak działa R:

Zastosowanie R w pewnym etapie powoduje tylko anulowanie terminów, które NA TYM KROKU zawierałyby przeciwne literały (być może będziemy musieli wyśledzić literały ujemne). Na przykład, oceńmy jako najpierw, aby obliczyć DNF 'na pierwszym węźle AND, otrzymujemy przed zastosowaniem R , ale po zastosowaniu R tracimy pierwsze z pierwszego nawiasu i otrzymujemy (gdzie pierwsze mogłoby mieć wirtualny NOT , gdybyśmy go śledzili) . Następnie zastosuj drugie AND, aby uzyskać

$$(x\lor y) \land (\lnot x \lor y) \land (x \lor \lnot y)$$ $$((x\lor y) \land (\lnot x \lor y))\land (x \lor \lnot y)$$ $$(x\lor y) \lor ((x\land y)\lor (y\land y))$$ $x$ $$(y) \lor (x\land y)\lor (y),$$ $y$$x$ $$((y) \lor (x\land y)\lor (y)) \lor ((x\land y)\lor (x\land y) \lor (x\land y)),$$ ale następnie R usuwa cały pierwszy nawias, ponieważ wirtualny NIE jest obecny (w tym przypadku nie musieliśmy śledzić poprzednich kroków, ale być może potrzebujemy w ogóle), pozostawiając lub po prostu $$((x\land y)\lor (x\land y) \lor (x\land y))$$ $$(x\land y)$$

Poprawność twierdzonego dowodu jest omawiana na blogu Luca Trevisana: https://lucatrevisan.wordpress.com/2017/08/15/on-norbert-blums-claimed-proof-that-p-does-not-equal- np /

W szczególności „anon” opublikował następujący odpowiedni komentarz:

„Tardos zauważył, że argumenty Razborova i Alona-Boppany przenoszą się na funkcję obliczoną przez wielomianowy obwód niemonotoniczny (funkcja jest niewielkim wariantem zbliżenia funkcji Lovasz theta na wykresie). Jeśli argumenty Berga i Ulfberga również ubiegać się o funkcję Tardosa (która jest intuicyjnie prawdopodobna, ponieważ ich dowód wydaje się opierać na dowodzie Razborova), to jasne jest, że obecne twierdzenie Bluma nie może być prawidłowe. Niestety autor nie omawia tego punktu. ”

Na bezpośrednie pytanie z „Michaiła” Aleksander Razborow potwierdza to (patrz post Michaił): rozumowania podane przez Berga i Ulfberga doskonale pasują do funkcji Tardos, a ponieważ tak jest, dowód Bluma jest koniecznie niepoprawny, ponieważ jest sprzeczny z jądrem szóstego twierdzenia w jego pracy. - A. Razborov

Moim zdaniem zdecydowanie rozwiązuje to pytanie, czy papier jest poprawny, czy nie (NIE jest poprawny!). Należy również zauważyć, że naprawa dowodu wydaje się trudna, ponieważ sama metoda dowodu wydaje się wadliwa.

Aktualizacja (2017/08/30) Norbert Blum opublikował następujący komentarz na swojej stronie arXiv:

Dowód jest błędny. Dokładnie wyjaśnię, na czym polega błąd. Potrzebuję na to trochę czasu. Wyjaśnię to na mojej stronie głównej

Gustav Nordh skomentował Twierdzenie 5 (strona 29). W szczególności funkcja

oblicza się funkcję, która ma tylko wtedy, gdy i oba , a tym samym jest monotoniczne. Wyrażenie powyżej funkcję stanowi „Standard sieci” (gdzie tylko zaprzeczenia są w dosłownym), którego węzły odpowiada literałów i , ich negacji, a każdy z tych określeń binarnych. Załóżmy, że węzeł wyjściowy sieci nazywa się .$1$$x$$y$$1$$\beta$$x$$y$$\beta$$g_0$

Papier Blum tworzy nową rozłączną postać normalną z która wydaje się być$DNF'_{\beta}(g_0)$$\beta$

Teraz, zgodnie z Twierdzeniem 5, każdy monomial w jest implikatorem . Ale jednym z monomialów w jest , co nie jest implikacją (ponieważ nie implikuje ), co jest sprzeczne z twierdzeniem. Jednakże, jak wskazano w uwagach przypisywanych Gustav Nordh i szczegółowego wyjaśnienia przez idolvon, ta pozorna rozbieżność zostanie rozwiązany poprzez odpowiednią i ekspansywnego interpretacji terminu „pochodzi” w definicji operatora redukcja .$DNF'_{\beta}(g_0)$$f$$DNF'_{\beta}(g_0)$$x$$f$$x=1$$f(x,y)=1$$R$

Czy można zastosować dekodowanie list kodów Reeda-Solomona, aby pokazać, że funkcja POLY Andreeva jest w P, podobnie jak Sivakumar w swoim członkostwie porównywalny artykuł ? A może wiadomo, że funkcja POLY jest NP-kompletna?

On updated jego arXiv powiedzieć jego dowód jest nieprawidłowy:

Dowód jest błędny. Dokładnie wyjaśnię, na czym polega błąd. Potrzebuję na to trochę czasu. Wyjaśnię to na mojej stronie głównej.

Blog Liptona i Regana ma tutaj dobrą dyskusję na wysokim poziomie z interesującym komentarzem na temat struktury dowodu.

Wskazują również na rodowód Bluma, który wykazał niższą granicę złożoności obwodu boolowskiego, która utrzymywała się przez ponad 30 lat. To oczywiście tylko „informacja dodatkowa”, ponieważ eksperci już poważnie badają dowody.

Także tutaj: https://www.quora.com/Whats-the-status-of-Norbert-Blums-claim-that-operatorname-P-neq-operatorname-NP

Cytując Alon Amit:

(osobista opinia, 14 sierpnia, później w ciągu dnia): Nie sądzę, żeby ten artykuł mógł się przyjrzeć. Głębokie twierdzenie, które zostało tak masowo zbadane, jak P ≠ NP, najprawdopodobniej zostanie rozwiązane za pomocą głębokich i dalekosiężnych nowych technik. Nie jest niemożliwe, że zostanie to rozwiązane przy niewielkim ulepszeniu znanych, istniejących metod, ale jest to bardzo, bardzo, bardzo mało prawdopodobne.

Jest mało prawdopodobne, aby była poprawna z następującego powodu: metoda aproksymacji jest na tyle ogólna, że ​​można ją udowodnić za pomocą dowolnej dolnej granicy. Jest to wynik z powodu Razborova. Dlaczego to jest problem? Ponieważ oznacza to, że metoda przybliżania nie będzie głównym postępem, może wyrażać wszystko, mięso będzie gdzie indziej. W gazecie nie ma takiego mięsa, co sugeruje, że autor najprawdopodobniej popełnia subtelny błąd, rodzaj błędu, który jest ukryty przed okiem, ale zasadniczo jest to założenie sugerujące odpowiedź. Dla tych, którzy nie są teoretykami złożoności: jest to bardzo dobry test węchu, jest równie prawdopodobne, że ktoś twierdzi, że zbudował rakietę w swojej piwnicy, aby za tydzień podróżować na Księżyc.

Więc gdzie jest ta subtelna pomyłka? Na blogu Trevisana znajduje się komentarz Lovetta sugerujący, jakie może być to ukryte założenie w twierdzeniu 6.

$NP-c$$P$

$C$$f$$f$$C$$m$

Funkcja boolowska ma tylko jedną tabelę prawdy, ale nie ma jednego wyrażenia algebraicznego, żaden problem nie ma tylko jednej funkcji boolowskiej, która ją rozwiązuje.

Niektóre (być może wszystkie) funkcje są izomorficzne (problemy nie są).

$NP=P$$m$$m$$f$$f$$f$