Pytania otagowane jako cc.complexity-theory

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

3
Złożoność decydowania, czy macierz jest całkowicie regularna
Matryca jest nazywana całkowicie regularną, jeśli wszystkie jej kwadratowe submatrice mają pełną rangę. Takie matryce zastosowano do budowy superkoncentratorów. Jaka jest złożoność decyzji, czy dana matryca jest całkowicie regularna w stosunku do racjonalności? Ponad skończonymi polami? Mówiąc bardziej ogólnie, nazwij matrycę całkowicie nieregularną, jeśli wszystkie kwadratowe podmacie wielkości co najwyżej …
1
Czy rozwiązywanie układów równań modulo w dla złożone?
Interesuje mnie złożoność rozwiązywania równań liniowych modulo k , dla dowolnego k (i ze szczególnym zainteresowaniem mocami pierwotnymi), w szczególności: Problem. Czy dla danego układu równań liniowych w nieznanych modulo istnieją jakieś rozwiązania?n kmmmnnnkkk W streszczeniu swojego artykułu Struktura i znaczenie klas logspace-MOD w klasach Mod k L , Buntrock, …
2
Minimalna niezadowalająca formuła 3-CNF
Obecnie jestem zainteresowany pozyskiwaniem (lub konstruowaniem) i badaniem formuł 3-CNF, które są niezadowalające i mają minimalny rozmiar. Oznacza to, że muszą składać się z jak najmniejszej liczby klauzul (najlepiej m = 8) i możliwie jak najmniejszej liczby odrębnych zmiennych (n = 4 lub więcej), tak że usunięcie co najmniej jednej …
1
Czy istnieje lepsza niż liniowa dolna granica dla faktoringu i dziennika dyskretnego?
Czy istnieją odniesienia, które zawierają szczegółowe informacje na temat dolnych granic obwodu dla konkretnych trudnych problemów pojawiających się w kryptografii, takich jak faktoring liczb całkowitych, problem logarytmu dyskretnego z liczbami pierwszymi / złożonymi i jego wariant nad grupą punktów krzywych eliptycznych (i ich wielowymiarowych odmian abelowych) i ogólne ukryty problem …
4
Złożoność obliczeniowa w finansach ilościowych
Prognozowanie rynku akcji jest trudne! Czy TCS może uczynić ten sentyment bardziej formalnym? Ostatnio zacząłem trochę myśleć o finansach i zastanawiałem się, w jaki sposób wiedza TCS może pomóc. Fundusze hedgingowe i firmy inwestycyjne wydają się cały czas korzystać z handlu algorytmicznego, uczenia maszynowego i sztucznej inteligencji, ale wyniki TCS …
5
Dlaczego w ogóle działają relacyjne bazy danych, biorąc pod uwagę teoretyczną wykładniczą złożoność wyszukiwania odpowiedzi (w wielkości zapytania)?
Wydaje się znane, że aby znaleźć odpowiedź na zapytanie w relacyjnej bazie danych , potrzebny jest czas i nie można pozbyć się wykładnika.D | D | | Q | | Q |QQQrereD| D || Q ||re||Q||D|^{|Q|}| Q ||Q||Q| Ponieważ może być bardzo duży, zastanawiamy się, dlaczego bazy danych w ogóle …
4
Jaka jest „właściwa” definicja górnej i dolnej granicy?
Niech będzie najgorszym czasem działania problemu na wejściu wielkości . Uczyńmy ten problem nieco dziwnym, ustalając dla ale dla .f(n)f(n)f(n)nnnf(n)=n2f(n)=n2f(n) = n^2n=2kn=2kn=2kf(n)=nf(n)=nf(n) = nn=2k+1n=2k+1n=2k+1 Więc jaka jest dolna granica problemu? Zrozumiałem, że to tylko dolna granica . Ale wiemy, że oznacza, że ​​istnieje stała , taka, że ​​dla wszystkich , …
1
Konsekwencje UP są równe NP
EDYCJA na 2011/02/08: Po znalezieniu i przeczytaniu niektórych odniesień postanowiłem rozdzielić oryginalne pytanie na dwa osobne. Oto część dotycząca UP vs NP, w części dotyczącej klas syntaktycznych i semantycznych zobacz Korzyści dla klas syntaktycznych i semantycznych . UPUP\mathsf{UP} (jednoznaczny czas wielomianowy, patrzwikiizoodla odniesienia) jest zdefiniowany jako języki ustalone przez maszynyNPNP\mathsf{NP} …
4
Parzystość i
Parzystość i są jak nierozłączne bliźniaki. Tak przynajmniej wyglądało przez ostatnie 30 lat. W świetle wyników Ryana wznowione zostanie zainteresowanie małymi klasami.AC0AC0AC^0 Furst Saxe Sipser do Yao do Hastad są ograniczeniami parzystości i losowymi. Razborov / Smolensky jest przybliżonym wielomianem z parzystością (ok, mod bramki). Aspnes i wsp. Stosują słaby …
1
Wizualizacja unikalnych gier
Jak zaprojektowałbyś zdjęcie ilustrujące unikalną hipotezę gier? Jest to prezentacja „bieżących wydarzeń” na temat unikalnych gier podczas następnego wspólnego spotkania AMS oraz broszura, która zostanie wydana. Przykłady tego rodzaju ilustracji wykonanych w przeszłości znajdują się na http://www.ams.org/meetings/lectures/current-events-bulletin a jeśli klikniesz na wydanie z 2006 roku, zobaczysz zdjęcie, którego Madhu Sudan …
1
Jaki jest „prawdziwy” powód, dla którego IP = PSPACE nie powoduje relatywizacji?
OOOcoNPO⊈IPOcoNPO⊈IPO{\sf coNP}^O \not\subseteq {\sf IP}^OcoNPO⊆PSPACEOcoNPO⊆PSPACEO{\sf coNP}^O \subseteq {\sf PSPACE}^OOOO Jednak widziałem tylko kilka osób, które wyjaśniają „bezpośrednio”, dlaczego wynik nie jest relatywizowany, a typową odpowiedzią jest „arytmetyzacja”. Po sprawdzeniu dowodu IP = PSPACE ta odpowiedź nie jest fałszywa , ale nie jest dla mnie zadowalająca. Wydaje się, że „prawdziwy” powód …
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.