Pytania otagowane jako algebraic-complexity

2
Program GCT Mulmuleya
Czasami twierdzi się, że teoria złożoności geometrycznej Ketana Mulmuleya jest jedynym wiarygodnym programem do rozstrzygania otwartych pytań teorii złożoności, takich jak pytanie P vs. NP. Było wiele pozytywnych komentarzy od słynnych teoretyków złożoności na temat programu. Według Mulmuleya osiągnięcie pożądanych rezultatów zajmie dużo czasu. Wejście w ten obszar nie jest …
3
Czy implikuje ?
O ile rozumiem, program teorii geometrycznej złożoności próbuje oddzielić , udowadniając, że permament macierzy o złożonej wartości jest znacznie trudniejszy do obliczenia niż wyznacznik.VP≠VNPVP≠VNPVP \neq VNP Pytanie, które zadałem po przejrzeniu dokumentów GCT: Czy to natychmiast oznaczałoby , czy jest to tylko duży krok w kierunku tego celu?P≠NPP≠NPP \neq NP
5
Mnożenie liczb całkowitych, gdy jedna liczba całkowita jest ustalona
Niech AAA będzie stałą dodatnią liczbą całkowitą o rozmiarze nnn bitów. Można odpowiednio wstępnie przetworzyć tę liczbę całkowitą. Biorąc pod uwagę kolejną dodatnią liczbę całkowitą BBB o rozmiarze mmm bitów, jaka jest złożoność mnożenia ABABAB ? ϵ = 0(max(n,m))1+ϵ(max(n,m))1+ϵ(\max(n,m))^{1+\epsilon}ϵ=0ϵ=0\epsilon=0
2
Czy istnieje teoria łącząca teorię kategorii / algebrę abstrakcyjną i złożoność obliczeniową?
Teoria kategorii i algebra abstrakcyjna zajmują się sposobem łączenia funkcji z innymi funkcjami. Teoria złożoności dotyczy tego, jak trudna jest funkcja do obliczenia. Dziwne jest dla mnie to, że nie widziałem, aby ktoś łączył te kierunki studiów, ponieważ wydają się one takimi naturalnymi parami. Czy ktoś już to zrobił? Jako …
3
Formalna reprezentacja pierścieni w obliczeniach
Czytając artykuł na temat stosowania metod algebraicznych do wykrywania niektórych indukowanych subgrafów, okazuje się, że ideał krawędzi jest ważnym narzędziem łączącym algebrę komutacyjną i teorię grafów. Skoro nie znam obliczeń obiektów algebraicznych, czy są jakieś dobre odniesienia lub książki na ten temat? Szczególność w reprezentowaniu pierścienia R na maszynie Turinga …
4
Czy istnieją znane funkcje z następującą właściwością sumy bezpośredniej?
To pytanie można zadać albo w ramach złożoności obwodów obwodów boolowskich, albo w ramach teorii złożoności algebraicznej, lub prawdopodobnie w wielu innych ustawieniach. Łatwo jest wykazać, licząc argumenty, że istnieją funkcje logiczne na wejściach N, które wymagają wykładniczo wielu bramek (choć oczywiście nie mamy żadnych wyraźnych przykładów). Załóżmy, że chciałbym …
1
Wymiar VC wielomianów nad tropikalnymi półksiężycami?
BPP\mathbf{BPP}P\mathbf{P}poly\mathrm{poly} (max,+)(max,+)(\max,+)(min,+)(min,+)(\min,+) Niech będzie na pół wieku. Zerowej wzorzec sekwencji z wielomianów jest podzbiorem , dla których istnieją , a taki sposób, aby dla wszystkich , f i ( x ) = Y IFF ı ∈ S . Oznacza to, że wykresy dokładnie tych wielomianów f i z i ∈ …
1
Kurs do nauki złożoności algebraicznej
Chcę się dowiedzieć o algorytmach algebraicznych i złożoności tysiąca. W szczególności interesuje mnie PIT. Czy istnieje zestaw notatek z wykładów, książek, prac i ankiet dla studentów, którzy przeczytali standardowy podręcznik o teorii, taki jak książka Sipsera lub podręcznik złożoności Arory-Baraka. Zestaw referencji będzie zawierał najnowsze zaawansowane wyniki.
3
Gwarancje twardości dla AES
Wiele kryptosystemów z kluczem publicznym ma pewnego rodzaju sprawdzalne zabezpieczenia. Na przykład kryptosystem Rabin jest tak samo trudny jak faktoring. Zastanawiam się, czy istnieje taki rodzaj możliwego do udowodnienia bezpieczeństwa dla kryptosystemów tajnych kluczy, takich jak AES. Jeśli nie, jakie są dowody na to, że złamanie takich kryptosystemów jest trudne? …
1
Pojemność jednoznacznie rozwiązanej układanki (USP)
W swoim kluczowym artykule Teoretyczne algorytmy grupowania macierzy Cohn, Kleinberg, Szegedy i Umans przedstawiają koncepcję unikatowej układanki (zdefiniowanej poniżej) i zdolności USP. Twierdzą oni, że Coppersmith i Winograd, w ich własnym papierze przełomowy Mnożenie macierzy poprzez ciąg arytmetyczny , „pośrednio” udowodnić, że zdolność USP jest 3/22/33/22/33/2^{2/3} . Twierdzenie to zostało …
2
Eliminacja gaussowska pod względem działania grupowego
Eliminacja Gaussa sprawia, że ​​wyznacznik macierzy obliczany jest w czasie wielomianowym. Zmniejszenie złożoności obliczania wyznacznika, które w przeciwnym razie jest sumą terminów wykładniczych, wynika z obecności alternatywnych znaków ujemnych (których brak sprawia, że ​​obliczenia są trwałe, tj. Trudniejszy niż problemy ). Prowadzi to do pewnego rodzaju symetrii w wyznaczniku, np. …
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.