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

232

Norbert Blum opublikował niedawno 38-stronicowy dowód, że . Czy to jest poprawne?PNP

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

Warren Schudy
źródło
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
Bjørn Kjos-Hanssen

Odpowiedzi:

98

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 )CgCNF(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 ggβCNF(g)DNF(g)CgkDgrCNFDNFDgrCgkDgr(mniej niż stała r) oraz w każdej klauzuli dla (mniej niż stała k).Cgk

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 gDNF(g)CNF(g)gβCgkDgrw 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.CgkDgrCgkCgkDgr

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).kβ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)?β

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 ' rCNF(g)DNF(g)CgkDgrgβCNF(g)DNF(g)CgkDgrCNF(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ł.CgrDgr

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 βCNFDNFg0β

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)CgrDgkCNFDNF

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 γ 2γ1γ2h1h2CNFβ(h1)CNFβ(h2)CgCNFβ(g)γ1γ2

idolvon
źródło
2
wydaje się być tym samym komentarzem na blogu RJL rjlipton.wordpress.com/2017/08/17/... czy to napisałeś? chciałem dodać pomysł: co jeśli kluczem jest rozważenie T0 / T1 wszystkich równych 1-bitów wr konwersji cnf-dnf / przybliżenia? jest znany przez Berkowitz 1982 jest to wystarczające, aby oddzielić P vs NP patrz „złożoność funkcji slice” / Wegener sciencedirect.com/science/article/pii/0304397585902099
vzn
6
@vzn Autor tego komentarza na blogu to „vloodin”. Autorem tej odpowiedzi jest „idolvon”. Permutacja liter daje wskazówkę, że autorzy nie są zbyt różni.
Clement C.
2
Ciekawe, czy po przesłaniu artykułu do ARXIV pojawiła się jakaś komunikacja publiczna z Blum?
Matt
9
@Matt Blum wycofał artykuł i zamieścił następujący komentarz na stronie arXiv artykułu: „Dowód jest błędny. Dokładnie wyjaśnię, na czym polega błąd. Potrzebuję na to trochę czasu. Wyjaśnię to strona główna ”
Gustav Nordh
Ta odpowiedź została potwierdzona jako poprawna przez Scott Aaronson, powołując się na innych (nienazwanych) recenzentów: scottaaronson.com/blog/?p=3409
cuniculus
95

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.

Michaił
źródło
2
Byłoby wspaniale, gdybyś mógł to rozwinąć. Czy wiadomo, że funkcja Tardos występuje w P?
Thomas
5
Funkcja Tardos jest w P i jest przybliżeniem funkcji Lovasz theta, która dla uzupełnienia grafu znajduje się między liczbą kliki a liczbą chromatyczną. Prawdziwą funkcją Lovasz theta jest monotoniczna funkcja wykresu. Pytanie brzmi jednak, czy przybliżenie to powoduje również powstanie monotonicznej funkcji wykresu (tylko funkcja monotoniczna unieważnia dowód). Czy ktoś może podać nam odniesienie do dokumentu Tardos, w którym jest on zdefiniowany, proszę?
idolvon
7
@idolvon Masz na myśli to: cs.cornell.edu/~eva/... To wyraźnie wskazuje, że funkcja φ jest poli-time funkcja obliczalna monotonia
PsySp
12
Dzięki! To w zasadzie to rozwiązuje - dowód Blooma musi być błędny. Teraz może być interesujące wskazanie błędu. Zajmę się tym i opublikuję komentarz na temat Liptona, jak w dawnych dobrych czasach, według prof. p Życzenia dzięcioła.
idolvon
1
@idolvon Tak, też tak myślałem. Argumenty Bluma powinny przenosić funkcję φ zgodnie z definicją zawartą w tym artykule, który stwierdza, że jest to monotoniczny i polytime obliczalny (trywialny z definicji).
PsySp
41

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 = 1DNF(g0)fDNF(g0)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 ) fDNF(g0)fDNF(g0)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 )DNF(g)gDNF(g0)

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ąfg0DNF(g0)RDNF(g0)fDNF(g0)

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?RDNF(g0)gDNF(g)gres(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α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ć

(xy)(¬xy)(x¬y)
((xy)(¬xy))(x¬y)
(xy)((xy)(yy))
x
(y)(xy)(y),
yx
((y)(xy)(y))((xy)(xy)(xy)),
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
((xy)(xy)(xy))
(xy)
Clement C.
źródło
6
Jestem na to sceptyczny (ale nie używam Facebooka, żeby coś powiedzieć) - Funkcja Andreeva (w artykule) jest podana jako dwustronny wykres z lewym i prawym zestawem wierzchołków równym GF (q), plus dowolny zestaw krawędzi i stopień związany. Pytanie brzmi, czy istnieje sposób wyboru dla każdego wierzchołka po lewej stronie jednego z jego sąsiadów, tak aby indukowana funkcja (od lewej do prawej) była wielomianem niskiego stopnia. Komentarz Lucy ma zastosowanie, gdy mamy dobry wybór sąsiada dla każdego lewego wierzchołka (ponieważ wtedy jest to po prostu interpolacja wielomianowa), ale nie jest dla mnie jasne, jak dokonać dobrego wyboru.
Andrew Morgan
@AndrewMorgan Zaktualizowałem odpowiedź CW.
Klemens C.
@Karl Wimmer: jeśli chodzi o pogodę, DNF ′ (g0) oblicza f, myślę, że należy użyć tego, że f jest monotoniczny. W Twierdzeniu 5 założono, że f jest monotoniczny.
idolvon,
zmieszany! czy to wszystko cytuje z posta na Facebooku? po kliknięciu powyższego linku do facebooka shachar lovett niektóre z powyższych odpowiedzi są dla mnie widoczne, ale inne nie są dla mnie widoczne. np. Karl Wimmer. czy jest to spowodowane pewnym przeglądem odpowiedzi znajomych na Facebooku? jeśli tak, to rozczarowuje i nie jest to zbyt dobre miejsce do publicznej dyskusji. może ktoś może zrobić zrzut ekranu? :( czy cytujesz rzeczy spoza posta na Facebooku? plz bądź ostrożny / uzupełnij o cytowania / adresy URL
od
O! dalsze badania to są również przytoczyć odpowiedzi od Baez blogu, który zawiera Wimmers odpowiadać etc johncarlosbaez.wordpress.com/2017/08/15/...
vzn
36

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
źródło
3
Opublikowałem to jako odpowiedź, ponieważ nie mam jeszcze uprawnień do publikowania komentarzy.
Gustav Nordh
11
Tak, tak rozumiem (ale mogę się mylić). Funkcja Tardos jest funkcją monotoniczną, która wynosi 1 na k-klikach i 0 na pełnych (k-1) wykresach stronicowych. O ile mogę stwierdzić, Berg i Ulfberg używają TYLKO tych właściwości w swoim dowodzie aproksymacji CNF-DNF dla CLIQUE, co dowodzi, że funkcja Tardos ma wykładniczą złożoność monotoniczną. Twierdzenie Bluma 6 mówi, że dolne granice złożoności monotonicznej przez aproksymację CNF-DNF dla funkcji monotonicznych, dają tę samą dolną granicę NON-monotoniczną. Dlatego funkcja Tardosa ma wykładniczą złożoność zgodnie z Twierdzeniem 6 (co jest fałszem).
Gustav Nordh
5
W takim przypadku wygląda na to, że rozstrzygnięcie tego punktu powinno być teraz głównym celem ... Nie sądzę, że jestem kompetentny lub wystarczająco kompetentny, aby to zrobić, ale (kciuki, co nie pomaga w pisaniu) inni są.
Klemens C.
3
Gdzie jest zdefiniowana ta funkcja Tardos, czy ktoś może odwołać się do artykułu? Oczywiście, istnieją funkcje niemonotoniczne, które oddzielają T0 ​​i T1, które są w P (łatwo zbudować powiedzmy, czy mamy pełny wykres z węzłami k), ale czy funkcja Tardos jest monotoniczna? Jeśli monotoniczny i oddziela T0 i T1, unieważnia dowód. Ale jeśli nie jest to monotonia, dowód może być nadal poprawny.
idolvon
4
Funkcja Tardos jest zdefiniowana w jej bardzo krótkim artykule znajdującym się tutaj: cs.cornell.edu/~eva/... Ponadto właściwości funkcji Tardos zostały szczegółowo omówione w [S. Jukna, Złożoność funkcji boolowskiej p. 1 272]
Gustav Nordh
25

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

(xy)(¬xy)(x¬y)

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ę .1xy1βxyβg0

Papier Blum tworzy nową rozłączną postać normalną z która wydaje się byćDNFβ(g0)β

xy(xy)

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β(g0)fDNFβ(g0)xfx=1f(x,y)=1R

kdog
źródło
2
Wygląda na to, że DNF 'dla tej formuły to (x AND y)
utwórz
2
@idolvon Masz rację, stosując alternatywną definicję na stronie 29. Ale główna definicja znajduje się na stronach 27-28 i przy tej definicji oryginalna analiza Nordha jest poprawna. Nie zamierzam przeskakiwać po gazecie i próbować zgadywać, co autor zamierzał, szczególnie gdy tekst definicji na stronach 27–28 jest w tym przypadku bardzo jasny. Także inne dowody w artykule wykorzystują definicję str. 27–28, a nie „alternatywną definicję” na stronie 29.DNF
kdog
2
Definicja na stronach 27-28 obejmuje użycie operatora R, który nie jest zdefiniowany, z wyjątkiem niejasnego zwrotu „pochodzi z trywialnego monomialu”. Jeśli przyjmiemy, że oznacza to, że „zostałyby anulowane, gdyby dosłownie były przestrzegane na tym etapie”, wówczas definicje są takie same. W każdym razie potrzebowałbyś NIEKTÓREJ interpretacji dla R. Ponieważ R jest tak ważne w rozdziale 6, ważna jest właściwa interpretacja, a faktycznie istnieje taka indukcyjna.
idolvon
2
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 ś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
(xy)(¬xy)(x¬y)
((xy)(¬xy))(x¬y)
(xy)((xy)(yy))
x
(y)(xy)(y),
idolvon
2
(gdzie pierwsze mogłoby mieć wirtualny NOT , gdybyśmy go śledzili). Następnie zastosuj drugie AND, aby uzyskać ale następnie R usuwa cały pierwszy nawias, ponieważ nie ma on wirtualnej obecności (w tym przypadku nie musieliśmy śledzić poprzednich kroków, ale być może potrzebujemy w ogóle), pozostawiając lub po prostuyx
((y)(xy)(y))((xy)(xy)(xy)),
((xy)(xy)(xy))
(xy)
idolvon
17

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?

Lance Fortnow
źródło
10
Lance, nie odpowiadam na twoje pytania. W czerwcu 1986 r. „Otwarty problem miesiąca” Davida Johnsona zapytał, czy problem Andreeva jest NP-zupełny. Patrz kolumna Davida kompletności NP w Journal of Algorithms 7: 2, s. 289–305. Nie jestem pewien, czy kiedykolwiek istniało rozwiązanie.
Ravi Boppana
1
Artykuł Johnsona z 1986 roku wyprzedza techniki wielomianowej rekonstrukcji i wyniki dekodowania list lat 90.
Lance Fortnow,
1
Oto mój pomysł, korzystając z zapisu w części 7 artykułu Norberta Bluma. Wielomian p będący rozwiązaniem problemu POLY można postrzegać jako słowo kodowe Reeda-Solomona. Wybierz funkcję f, losowo wybierając krawędź z każdego wierzchołka w A. To f powinno zgadzać się zpw znacznie większym niż 1 / q ułamku danych wejściowych. Następnie możemy użyć dekodowania listy na f, aby utworzyć wielomianowo długą listę możliwości dla p i możemy sprawdzić każdą z nich.
Lance Fortnow,
1
O ile nie zrozumiem twojego algorytmu, używając algorytmu Guruswami-Sudan, można list-dekodować, jeśli liczba umów wynosi co najmniej , gdzie jest stopniem , a my jesteśmy zainteresowani tą sprawą kiedy , co oznacza, że ​​potrzebujemy znacznie więcej niż tylko frakcyjnej umowy . dpdqddp 1dqlogq1q
4
@Matt Zakładając, że poprawnie przeczytałem powyższe, funkcja ta jest tą Blum, dla której twierdzi się, że udowodniono złożoność obwodu wielobiegunowego. Ale jeśli jest w P, musi mieć złożoność obwodu wielomianowego, co jest sprzeczne z rzekomym dowodem P vs. NP.
Klemens C.
14

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.

Mehrdad
źródło
9

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.

kodlu
źródło
3

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.

Jacek
źródło
11
To nie jest argument (prawidłowa opinia, i przyznaję, że się z nią podzielam, ale nie jest to uzasadniony argument, który moim zdaniem powinniśmy tutaj mieć). Tego rodzaju rzeczy zdarzały się wcześniej .
Clement C.
8
Tak, nie kłóciłem się. Wystarczy odpowiedzieć na pytanie „gdzie omawiany jest ten artykuł”, a następnie podsumować wspomnianą dyskusję do tego momentu.
Jack
2

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.

Sceptyk
źródło
fajny / odpowiedni punkt; fyi razborovs „no go” thm jest „metodą przybliżenia” (1989) people.cs.uchicago.edu/~razborov/files/approx.pdf, ale uważam, że ten dowód nie jest zbyt dobrze przeanalizowany. należy dokładnie zrozumieć, czy określone warunki nie wykraczają poza słowa „metoda przybliżenia”, które przeszły przez korekty / zmiany / udoskonalenia itp. od momentu powstania przez Razborova. te dokładne warunki najwyraźniej nie są zbytnio analizowane przez późniejszych badaczy. drugą główną barierą są naturalne dowody razborov / rudich en.wikipedia.org/wiki/Natural_proof
vzn
przegłosowano, ponieważ treść tej odpowiedzi została już uwzględniona w poprzednich odpowiedziach.
weryfikacja
-2

NPcP

CffCm

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=Pmmfff

Ixer
źródło