Matematyczne implikacje teorii złożoności przypuszcza poza TCS

Czy znasz ciekawe konsekwencje (standardowych) przypuszczeń w teorii złożoności w innych dziedzinach matematyki (tj. Poza informatyką teoretyczną)?

Wolałbym odpowiedzi gdzie:

• hipoteza teorii złożoności jest tak ogólna i standardowa, jak to możliwe; Nie przeszkadzają mi również konsekwencje twardości określonych problemów, ale byłoby miło, gdyby powszechnie uważano, że problemy są trudne (lub przynajmniej zostały zbadane w kilku artykułach)

• implikacją jest stwierdzenie, o którym nie wiadomo, że jest prawdziwe bezwarunkowo, lub inne znane dowody są znacznie trudniejsze

• im bardziej zaskakujące połączenie, tym lepiej; w szczególności implikacją nie powinno być stwierdzenie wprost dotyczące algorytmów

Połączenia „gdyby świnie mogły latać, konie zaśpiewałyby” również są w porządku, o ile latające świnie pochodzą z teorii złożoności, a śpiewające konie z jakiejś dziedziny matematyki spoza informatyki.

To pytanie jest w pewnym sensie „odwrotnością” pytania, jakie mieliśmy o zaskakujące zastosowania matematyki w informatyce. Dick Lipton napisał na blogu dokładnie takie zdanie: pisze o konsekwencjach przypuszczenia, że ​​faktoring ma dużą złożoność obwodów. Konsekwencje są takie, że niektóre równania diofantyczne nie mają rozwiązań, rodzaj stwierdzenia, które może być bardzo trudne do udowodnienia bezwarunkowo. Post opiera się na pracy z Danem Bonehem, ale nie mogę znaleźć artykułu.

EDYCJA: Jak zauważa Josh Grochow w komentarzach, jego pytanie dotyczące zastosowania TCS do matematyki klasycznej jest ściśle powiązane. Moje pytanie jest z jednej strony bardziej liberalne, ponieważ nie nalegam na ograniczenie „klasycznej matematyki”. Myślę, że ważniejszą różnicą jest to, że nalegam na udowodnioną implikację od przypuszczenia złożoności do stwierdzenia w dziedzinie matematyki poza TCS. Większość odpowiedzi na pytanie Josha nie jest tego typu, ale podaje techniki i koncepcje przydatne w klasycznej matematyce, które zostały opracowane lub zainspirowane przez TCS. Niemniej jednak przynajmniej jedna odpowiedź na pytanie Josha jest idealną odpowiedzią na moje pytanie: artykuł Michaela Freedmanaktóry jest motywowany pytaniem identycznym z moim, i dowodzi twierdzenia w teorii węzłów, uwarunkowanego . Twierdzi, że twierdzenie wydaje się być poza zasięgiem obecnych technik teorii węzłów. Zgodnie z twierdzeniem Tody, jeśli wówczas hierarchia wielomianowa załamie się, więc założenie jest całkiem prawdopodobne. Interesują mnie inne podobne wyniki.P # P = N $\mathsf{P}^{\#P} \ne \mathsf{NP}$$\mathsf{P}^{\#P} = \mathsf{NP}$

Oto kolejny przykład z teorii grafów. Twierdzenie o mniejszym wykresie mówi nam, że dla każdej klasy niekierowanych wykresów, które są zamknięte dla nieletnich, istnieje skończony zbiór przeszkód O b s ( G ) taki, że wykres jest w G wtedy i tylko wtedy, gdy nie zawiera wykresu w O b s ( G ) jako nieletni. Jednak twierdzenie wykres moll jest z natury nonconstructive i nie mówi nam nic o tym, jak duże są te zestawy przeszkodowe, czyli ile zawiera wykresy dla konkretnego wyboru G .$\mathcal{G}$$\mathcal{Obs(G)}$$\mathcal{G}$$\mathcal{Obs(G)}$$\mathcal{G}$

W „ Zbyt wielu przeszkodach dla drobnych porządków” Michael J. Dinneen wykazał, że przy prawdopodobnej hipotezie złożoności teoretycznej rozmiary kilku takich zestawów przeszkód mogą być duże. Weźmy na przykład sparametryzowaną klasę grafów z rodzaju co najwyżej k . W miarę wzrostu k możemy oczekiwać, że zbiory przeszkód O b s ( G k ) będą coraz bardziej skomplikowane, ale o ile? Dinneen pokazał, że jeśli hierarchia wielomianowa nie zapadnie się do swojego trzeciego poziomu, wówczas nie ma wielomianu p, tak że liczba przeszkód w O b s$\mathcal{G}_k$$k$$k$$\mathcal{Obs}(\mathcal{G}_k)$$p$jest ograniczone przezp(k). Ponieważ liczba drobnych przeszkód dla posiadania rodzaju zero (tj. Bycia planarnym) wynosi tylko dwa ( O b s ( G 0 )={ K 5 , K 3 , 3 }), ten wzrost wielobiegunowy nie jest od razu oczywisty (chociaż w to wierzę) można udowodnić bezwarunkowo). Zaletą wyniku Dinneen jest to, że ma on zastosowanie do rozmiarów zestawów przeszkód odpowiadającychdowolnemusparametryzowanemu zestawowi drobnych ideałów G k, dla których decyduje najmniejszy$\mathcal{Obs}(\mathcal{G}_k)$$p(k)$$\mathcal{Obs}(\mathcal{G}_0) = \{K_5, K_{3,3}\}$$\mathcal{G}_k$$k$dla których jest NP-twardy; we wszystkich takich sparametryzowanych drobnych ideałach rozmiary zestawów przeszkód muszą rosnąć w sposób wielobiegunowy. $G \in \mathcal{G}_k$

Oto przykład: złożoność obliczeniowa i asymetria informacyjna produktów finansowych Arory, Baraka i Ge pokazują, że może ona być trudna obliczeniowo (tj. Trudna NP) do prawidłowej wyceny instrumentów pochodnych - używają najgęstszego podgraphu jako wbudowanego twardego problemu.

W tym samym i wiele wcześniejszych wersach znajduje się słynny artykuł Bartholdiego, Tovey i Tricka na temat trudności w manipulowaniu wyborami.

Jak sugeruje Sasho, moja odpowiedź na pytanie „ Zastosowanie TCS do matematyki klasycznej? ” Brzmi:

$L$$\tau$

$L$

$\tau$$p$$\tau$$(1+\tau)^c$$c$

$S_{2^k}$$S_{2^k}$$2^{\delta k}$

Jest to bardzo zgodne z duchem wspomnianego wcześniej artykułu Mike'a Freedmana.

wydaje się, że wiele pytań dotyczących separacji klas złożoności TCS ma poważne implikacje w matematyce. w szczególności pytanie P =? NP wydaje się mieć bardzo głębokie powiązania między wieloma dziedzinami, w tym matematyką. kilka znaczących przypadków w tym obszarze:

• Wykazano, że problem Hilbertsa Nullstellensatza sformułowany na początku XX wieku ma podatność na wycinanie ściśle związaną ze złożonością P vs NP, np. W NIETRAKCYJNOŚCI NULLSTELLENSATZA HILBERTA I WERSJI ALGEBRAICZNEJ „NP ̸ = P?” Autorstwa Shub / Smale. jest to ciągły obszar badań np. w dziedzinie algebry komputerowej, kombinatoryki i złożoności: Nullstellensatz Hilberta i problemów NP-zupełnych autorstwa Margulies.

• Twierdzenie Faginsa (wikipedia):

  Twierdzenie Fagina jest wynikiem opisowej teorii złożoności, która stwierdza, że ​​zbiór wszystkich właściwości wyrażalnych w egzystencjalnej logice drugiego rzędu jest właśnie klasą złożoności NP. Jest to niezwykłe, ponieważ jest to charakterystyka klasy NP, która nie odwołuje się do modelu obliczeniowego takiego jak maszyna Turinga.

  główna / zaskakująca implikacja P = NP oznaczałaby, że wszystkie twierdzenia logiczne drugiego rzędu mogłyby być skutecznie obliczone.

• innym przypadkiem jest to, że istnieją różne kompletne problemy związane z NP, wyrażone głównie tylko w kategoriach matematycznych (np. brak odniesienia do pojęć TCS takich jak TM, niedeterminizm itp.). lista ta mogłaby być bardzo duża, gdyby teorię grafów (dość rozsądnie) traktować jako matematykę. jednak nawet wąskie interpretacje „matematyki” prowadzą do przypadków, na przykład w teorii liczb.

  $a,b,c$$x\le c$$x^2\equiv a\pmod b$

  • Czy istnieje naturalny problem natury naturalnej, który jest NP-zupełny? tcs.se
  • teoria liczb i NP pełny przepływ matematyczny