Pytania otagowane jako cc.complexity-theory

P a NP i inne obliczenia ograniczone do zasobów.

1
Słynny papier P = BPP Impagliazzo i Wigdersona
Czytam słynny artykuł Impagliazzo i Wigdersona w 1997 roku. Ponieważ jestem nowy w tej dziedzinie, a artykuł jest zwięzłą wersją konferencji, mam trudności z podążeniem za nimi. W szczególności niektórym z ich nowych twierdzeń brakuje dowodów. Według mojej najlepszej wiedzy nie opublikowano wersji czasopisma.P = B P PP.=bP.P.\mathsf P=\mathsf{BPP} Szukam …
1
Na wykresie Izomorfizm Kompletne problemy
Jestem zainteresowany badaniem kompletnych problemów z Graph Isomorphism (GI). W artykule „Problemy wielomianowo równoważne z izomorfizmem grafowym” Kellogga S. Bootha (1979) udowodnili, że wiele podstawowych problemów jest uzupełnionych GI przy użyciu technik zastępowania krawędzi, technik kompozycji itp. Chciałbym nauczyć się kilku innych technik, które są używane w ostatnich artykułach. Czy …
2
Jak trudno policzyć liczbę lokalnych optymów dla problemu w PLS?
W przypadku wielomianowego problemu wyszukiwania lokalnego wiemy, że musi istnieć co najmniej jedno rozwiązanie (lokalne optimum). Jednak może istnieć wiele innych rozwiązań, jak trudno jest policzyć liczbę rozwiązań problemu z kompletnym PLS? Jestem szczególnie zainteresowany w problemu decyzyjnego: nie wystąpienie tego problemu PLS-complete mają dwa lub więcej rozwiązań? Czy złożoność …
2
Czy istnieje wytłumaczenie trudności w udowodnieniu kwadratowych dolnych granic dla interesujących problemów NP?
To kontynuacja mojego poprzedniego pytania: Najbardziej znana deterministyczna złożoność czasu dolna granica naturalnego problemu w NP Uważam za zdumiewające, że nie byliśmy w stanie udowodnić żadnego kwadratowego deterministycznego czasu w dolnej granicy jakiegokolwiek interesującego problemu NP, na który ludzie dbają i starają się zaprojektować lepsze algorytmy. Nasza hipoteza o wykładniczym …
1
Złożoność obliczania średniej odległości wykresu
Niech d ( G ) jest średnią odległość podłączonego wykresie G .ad(G)ad(G)\rm{ad}(G)G.G.G. Jeden sposób obliczenia jest przez sumowanie elementów D ( G ) , macierz na odległość G i skalowanie sumę odpowiednio.ad(G)ad(G)\rm{ad}(G)D(G),D(G),D(G),GGG Jeśli grafem wyjściowym jest drzewo, to wiadomo, że średnią odległość można obliczyć w czasie liniowym (patrz B.Mohar, T.Pisanski …
1
Relatywizowany świat, w którym
Chciałabym wiedzieć, czy istnieje zrelatywizowane świat, w którym . Jestem również zainteresowany, aby wiedzieć, czy istnieje zrelatywizowane świat, w którym P B ≠ N P B = P P B .P.ZA= N P.ZA≠ P PZAPA=NPA≠PPA{\bf P^A}={\bf NP^A}\not = {\bf PP^A}P.b≠ N P.b= P PbPB≠NPB=PPB{\bf P^B} \not = {\bf NP^B} = …
1
Sztywność matrycy i zastosowania matryc o niskiej sztywności
Około jedna matryca stopnia jest uważane za sztywne, jeśli się do jego pozycję do , trzeba zmiany co najmniej n ^ {1 + \ epsilon} jego pozycji, dla niektórych \ epsilon > 0 .nnnn n1+ϵϵ>0n2n2\frac{n}{2}n1+ϵn1+ϵn^{1+\epsilon}ϵ>0ϵ>0\epsilon > 0 Jeśli n×nn×nn \times n macierzy AAA jest sztywny, to najmniejszy program linii prostej …
1
Świadkowie oprogramowania matematycznego
Podobnie jak wiele osób, jestem zapalonym użytkownikiem oprogramowania matematycznego, takiego jak Mathematica i Maple. Jednak coraz bardziej frustruje mnie wiele przypadków, w których takie oprogramowanie po prostu daje złą odpowiedź bez ostrzeżenia. Może się to zdarzyć podczas wykonywania wszelkiego rodzaju operacji, od prostych sum do optymalizacji wśród wielu innych przykładów. …
2
Oszukiwanie
Mam kilka pytań dotyczących oszukiwania obwodów o stałej głębokości. Wiadomo, że -wise niezależności konieczne oszukać A C 0 obwody głębokości D , gdzie n jest wielkości wejściowych. Jak można to udowodnić?logO ( d)( n )logO(d)⁡(n)\log^{O(d)}(n)A C.0AC0AC^0reddnnn Ponieważ powyższe jest prawdziwe, każdy generator pseudolosowy, który głupcy C 0 obwody głębokości D …
2
Problem egzaminatora (jednolite generowanie instancji / odpowiedzi decyzji SAT)
Asystentowi kursu udało się napisać program, który (deterministycznie) generuje trudne pytania egzaminacyjne. Teraz chciałaby napisać program, który generuje odpowiednie odpowiedzi. Problem egzaminatora pyta, czy jest to zawsze możliwe; przez egzaminatora Hipoteza stwierdza, że zakładając, P ≠ N PP.≠N.P.\mathsf{P} \neq \mathsf{NP} , to nie : wymyślanie problemów jest łatwiejsze niż wymyślanie …
1
Górna granica stopnia funkcji boolowskiej pod względem jej czułości
Bardzo interesującym otwartym problemem w badaniu miar złożoności funkcji boolowskiej jest tak zwana hipoteza wrażliwości vs. blokowa. Informacje na temat wrażliwości kontra czułości bloków można znaleźć na następującym blogu S. Aaronsona na stronie http://www.scottaaronson.com/blog/?p=453 . Według mojej najlepszej wiedzy, najlepszą górną granicą znaną na w kategoriach s ( f ) …
1
Wyniki dla niższych granic / twardości w Noisy Parity (LWE)
Niektóre tło: Chciałbym znaleźć „mniej znane” dolne granice (lub wyniki twardości) dla problemu Uczenie się z błędami (LWE) i ich uogólnienia, takie jak Uczenie się z błędami przez pierścienie. W celu uzyskania szczegółowych definicji itp. Oto miła ankieta przeprowadzona przez Regev: http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf Standardowym rodzajem założenia w stylu (R) LWE jest …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.