Nekrologi martwych przypuszczeń

Szukam domysłów na temat algorytmów i złożoności, które przez pewien czas były postrzegane przez wielu jako wiarygodne, ale później zostały one obalone lub przynajmniej niewiary, z powodu narastających kontr-dowodów. Oto dwa przykłady:

1. Hipoteza o losowej wyroczni: relacje między klasami złożoności, które dotyczą prawie wszystkich relatywizowanych światów, dotyczą również przypadku nie relatywizowanego. Zostało to obalone przez wynik , a pokazując, że dla prawie wszystkich losowych wyroczni , zobacz Losowa hipoteza Oracle jest fałszywa .I P X ≠ P S P A C E X$IP=PSPACE$$IP^X\neq PSPACE^X$$X$

2. Losowość ograniczonego błędu prawidłowo wydłuża moc czasu wielomianowego (tj. ). Wierzono to przez pewien czas, ale później, ze względu na wyrafinowane wyniki derandomizacji i ich związki ze złożonością obwodu, przeciwna hipoteza ( ) stała się powszechna (choć nadal otwarta).P = B P $P\neq BPP$$P=BPP$

Jakie są inne przypuszczenia, które nie zdały próby czasu?

$\mathsf{NL} \neq \mathsf{coNL}$ . Przed uzyskaniem wyniku, że te dwa były równe, myślę, że powszechnie uważano, że są różne, analogicznie do przekonania, że (tj. Ogólna zasada, że ​​„niedeterminizm i współ- niedeterminizm jest inny ”; okazało się to fałszywe w ramach ograniczeń złożoności przestrzeni, które były co najmniej logarytmiczne).$\mathsf{NP} \neq \mathsf{coNP}$

Przed uważano, że możliwe jest, że nawet nie było zawarte w : w Fortnow-Sipser 1988 przypuszczali, że tak jest i podali wyrocznia, w stosunku do której była to prawda.$\mathsf{IP} = \mathsf{PSPACE}$$\mathsf{coNP}$$\mathsf{IP}$

Programy rozgałęziające o stałej szerokości wymagają więcej niż wielomianu do zliczenia : po tym, jak Furst-Saxe-Sipser i Ajtai w 1981 roku wykazali, że obwody AC ⁰ nie mogą się liczyć, naturalnym następnym krokiem wydaje się być pokazanie, że programy rozgałęziające o stałej szerokości wielomianu długość nie mogła się liczyć, co powszechnie zakładano. David Barrington w 1986 roku wykazał, że nie tylko mogą liczyć, ale są równoważne z NC ¹ .

-conjecture: To każdy deterministyczny algorytm wymaga czasu.$\mathsf{3SUM}$$\mathsf{3SUM}$$\Omega(n^2)$

Zostało to obalone w 2014 roku przez Allana Grønlunda i Setha Pettie, którzy podali deterministyczny algorytm działający w czasie [1].$O(n^2/(\log n/\log \log n)^{2/3})$

[1] Trójkąty, zwyrodnienia i trójkąty miłosne. Allan Grønlund i Seth Pettie. W Foundations of Computer Science (FOCS) 2014, s. 621–630. arXiv: 1404.0799 [cs.DS]

Rozwiązanie dziesiątego problemu Hilberta autorstwa Davisa, Matiyasevicha, Putnama i Robinsona, pokazujące, że rekurencyjnie policzalne zestawy są właśnie zestawami diofantycznymi.

(Odtwarzam tutaj post na blogu , Hindsight , sprzed kilku lat, jak sugerowano w komentarzach).

Z przeglądu Georga Kreisela „ Problem decyzyjny dla wykładniczych równań diofantycznych” autorstwa Martina Davisa, Hilary Putnam i Julii Robinson, Ann. matematyki. (2), 74 (3) , (1961), 425–436. MR0133227 (24 # A3061) .

W niniejszym dokumencie ustalono, że każdy rekurencyjnie wymienny (re) zbiór może być egzystencjalnie zdefiniowany w kategoriach potęgowania. […] Te wyniki są powierzchownie związane z dziesiątym problemem Hilberta dotyczącym (zwykłych, tj. Nieeksponencjalnych) równań diofantycznych. Dowód wyników autorów, choć bardzo elegancki, nie wykorzystuje faktów rekondycjonowanych w teorii liczb ani w teorii zbiorów, a więc prawdopodobne jest, że obecny wynik nie jest ściśle związany z dziesiątym problemem Hilberta. Również nie jest całkowicie prawdopodobne, że wszystkie (zwykłe) problemy diofantyny są równomiernie redukowane do tych w określonej liczbie zmiennych o ustalonym stopniu, co miałoby miejsce, gdyby wszystkie zbiory były diofantyną.

Oczywiście, mój ulubiony cytat w związku z dziesiątym problemem pochodzi od Przedmowy Martina Davisa do dziesiątego problemu Jurija Matiyasevicha Hilberta .

W latach sześćdziesiątych często miałem okazję wykładać na temat dziesiątego problemu Hilberta. W tym czasie wiadomo było, że nierozwiązywalność będzie wynikać z istnienia pojedynczego równania diofantycznego, które spełnia warunek sformułowany przez Julię Robinson. Stworzenie takiego równania wydawało się jednak niezwykle trudne i rzeczywiście panowała opinia, że ​​istnieje małe prawdopodobieństwo, aby istniało. W moich wykładach podkreślałem ważne konsekwencje wynikające z dowodu lub dyskomfortu istnienia takiego równania. Nieuchronnie w okresie pytań zostałbym poproszony o opinię na temat tego, jak potoczą się sprawy, i miałem gotową odpowiedź: „Myślę, że hipoteza Julii Robinson jest prawdziwa i zostanie udowodniona przez sprytnego młodego Rosjanina”.

Program Hilberta i jego „przypuszczenie” o rozstrzygalności teorii formalnych. Został sformułowany na początku lat dwudziestych XX wieku i był realizowany przez niego i jego współpracowników na Uniwersytecie w Getyndze oraz w innych miejscach w latach dwudziestych i trzydziestych XX wieku.

„Dzięki tym nowym podstawom matematyki - które można odpowiednio nazwać teorią dowodu - wierzę, że raz na zawsze rozwiążę podstawowe pytania matematyki, przekształcając każde stwierdzenie matematyczne w konkretnie dającą się wykazać i rygorystycznie dającą się wyprowadzić formułę, a tym samym przenosząc cały kompleks pytań z dziedziny czystej matematyki ”.

Powszechnie wiadomo, że propozycje Hilberta „rozbiły się” (dość szybko [1931]) w twierdzenie Godela o niekompletności .

Ładny przegląd programu Hilberta i późniejszych wydarzeń znajduje się w: Richard Zach; Program Hilberta wtedy i teraz; Podręcznik filozofii nauki. Tom 5: Filozofia logiki; 2006

Zobacz także odpowiedź Andrésa Caicedo na inny aspekt tej historii: dziesiąty problem Hilberta, który został rozwiązany dopiero w 1970 roku.

W wykładzie Madhu Sudan * stwierdził, że istnieje przekonanie, że istnieje tak że , poprzez programowanie półfinałowe, przed potwierdzeniem trzybitowego twierdzenia PCP Håstad.$s > 1/2$$\text{PCP}_{1,s}[ \log n, 3] \subseteq \text{P}$

Rzeczywiście SDP pokazuje , ściśle wiążąc się ze złożonością takich PCP.$\text{PCP}_{1,1/2}[ \log n, 3] = \text{P}$

(* Znalazłem ten wykład Madhu opublikowany w „Teorii złożoności obliczeniowej pod redakcją Rudich / Wigderson”)

domniemania obejmują spektrum od formalnego do nieformalnego. na przykład słynna hipoteza Hilberta o rozstrzygalności matematyki została sformalizowana w kilka problemów, np. 10. problem Hilberta, ale była to również bardziej nieoficjalna hipoteza obejmująca całą dziedzinę. może być również postrzegany jako proponowany program badawczy.

jednym łatwym przepisem na znalezienie takiego „nekrologu martwych przypuszczeń” byłoby rozważenie stwierdzenia „meta” „[x] przypuszczenie mogłoby zostać udowodnione za mojego życia”. literatura matematyczna jest pełna takich stwierdzeń / oczekiwań, które okazały się „fałszywe” w sensie całkowitego odrzucenia oczekiwań dotyczących trudności i dostępności dowodu. klasyczna jest hipoteza Riemanna, otwarta od ponad półtora wieku. zastosowanie tego samego modelu do teorii złożoności nie jest tak łatwe, ponieważ teoria złożoności jest znacznie młodszą dziedziną naukową. Oto jednak kluczowy przykład.

wczesne odkrycie problemu P vs NP (teraz otwarte 4 i 50 lat) było swego rodzaju niewinnością, ponieważ pierwotni badacze tego nie zrobili i nie mogli sobie wyobrazić, jak trudny lub przekrojowy byłby problem. w celu uściślenia tego, rozważ dziedzinę złożoności obwodów wynalezioną na początku lat 80. XX wieku, np. przez Sipsera. był to program badawczy nieco podobny do Hilberta zamontowanego częściowo do ataku P przeciwko NP. niektóre historyczne wyniki podsumowuje Arvind w tym streszczeniu / wstępie Kolumna złożoności obliczeniowej, BEATCS 106 :

Lata 80. były złotym okresem dla dolnych granic złożoności obwodu logicznego. Nastąpiły poważne przełomy. Na przykład dolna granica wielkości wykładniczej Razborowa dla monotonicznych obwodów boolowskich obliczających funkcję Clique i dolne granice wielkości wielobiegowej Razborova-Smoleńskiego dla obwodów o stałej głębokości z bramkami MOD _p dla liczby pierwotnej p. Wyniki te sprawiły, że naukowcy optymistycznie oceniają postępy w zakresie pytań o dużej dolnej granicy i separacji klas złożoności. Jednak w ciągu ostatnich dwóch dekad optymizm stopniowo przerodził się w rozpacz. Nadal nie wiemy, jak udowodnić superpolinomalne dolne granice dla obwodów o stałej głębokości z bramkami MOD ₆ dla funkcji obliczalnej w czasie wykładniczym.

były dwa kluczowe dokumenty, które zestrzeliły nadzieje w terenie. Razborov miał świetne / sławne wyniki w funkcji Clique, ale potem napisał dwa przeciwne artykuły. jeden artykuł wykazał, że dopasowanie, problem czasu P, wymaga wykładniczych obwodów monotonicznych i dlatego w pewnym sensie podejście obwodu monotonicznego do dolnych granic zostało udaremnione z powodu braku zgodności złożoności z obwodami niemonotonowymi („kompletnymi”) (wciąż nie w pełni zrozumiany).

zostało to rozwinięte w jego słynnej pracy „ Naturalne dowody” wspólnie z Rudichem, w której wykazano, że wszystkie wcześniejsze dowody dolnej granicy obwodu podlegają szczególnemu wzorowi, który ma udowodnioną słabość w sensie sprzeczności z przypuszczalnymi dolnymi granicami na twardych generatorach liczb losowych z kryptografia.

więc do pewnego stopnia obwody „spadły z łaski”. nadal jest to ogromny obszar badań, ale konwencjonalna mądrość, poparta wynikami technicznymi, głosi, że do uzyskania dobrych wyników w tej dziedzinie, o ile to w ogóle możliwe, wymagany byłby jakiś specjalny, jak dotąd nieznany wzór / struktura dowodowa. w rzeczywistości podobnie można sugerować, że nawet „silne dolne granice w teorii złożoności” są obecnie postrzegane jako niezwykle trudne i nie było to powszechnie oczekiwane / przewidywane w młodszych czasach. ale z drugiej strony sytuuje ich to w trudnej sytuacji / znaczeniu / znaczeniu z dużymi (otwartymi) problemami matematyki.