Pytania otagowane jako average-case-complexity

2
Status światów Impagliazzo?
W 1995 r. Russell Impagliazzo zaproponował pięć światów złożoności: 1- Algorytmika: ze wszystkimi niesamowitymi konsekwencjami.P.= NP.P.=N.P.P=NP 2- Heuristica: problemy kompletne są trudne w najgorszym przypadku ( ), ale można je skutecznie rozwiązać w przeciętnym przypadku.N.P.N.P.NPP.≠ N.P.P.≠N.P.P \ne NP 3- Pessiland: Występują problemy z niepełną średniej wielkości przypadków , ale funkcje …
2
Paradygmaty analizy złożoności algorytmów
Analiza najgorszych i średnich przypadków to dobrze znane miary złożoności algorytmu. Niedawno wygładzona analiza pojawiła się jako kolejny paradygmat wyjaśniający, dlaczego niektóre algorytmy wykładnicze w najgorszym przypadku działają tak dobrze w praktyce, na przykład algorytm simpleksowy. Moje pytanie brzmi - czy istnieją jakieś inne paradygmaty do pomiaru złożoności algorytmu? Szczególnie …
1
Utrzymanie porządku na liście w w Czas
Problem z utrzymaniem porządku (lub „utrzymaniem porządku na liście”) polega na obsłudze operacji: singleton: tworzy listę z jednym elementem, zwraca do niej wskaźnik insertAfter: dany wskaźnik do elementu wstawia nowy element po nim, zwracając wskaźnik do nowego elementu delete: dany wskaźnik do elementu usuwa go z listy minPointer: biorąc pod …
2
Jaka jest najgorsza złożoność sita z polem liczbowym?
Biorąc kompozytu Pole numeru sita ogólnie najlepiej znane algorytm faktoryzacji całkowitymi faktoryzacji N . Jest to algorytm randomizowany i otrzymujemy oczekiwaną złożoność O ( e √N∈NN∈NN\in\Bbb NNNNdo współczynnikaN.O(e649√(logN)13(loglogN)23)O(e649(log⁡N)13(log⁡log⁡N)23)O\Big(e^{\sqrt{\frac{64}{9}}(\log N)^{\frac 13}(\log\log N)^{\frac 23}}\Big)NNN Szukałem informacji o złożoności najgorszych przypadków w tym randomizowanym algorytmie. Nie mogę jednak znaleźć informacji. (1) Jaka jest …
2
Warianty bezpośrednich twierdzeń o produktach
Bezpośrednie twierdzenie o produkcie, nieformalnie, mówi, że obliczenie instancji funkcji f jest trudniejsze niż jednorazowe obliczenie f .kkkfafffaff Typowe bezpośrednie twierdzenia o produktach (np. XOR Lemma Yao) patrzą na złożoność średnich przypadków i twierdzą (bardzo z grubsza), że nie może być obliczone przez obwody o wielkości s z prawdopodobieństwem większym …
1
Złożoność przestrzeni dla średnich przypadków
Próbuję znaleźć problemy, których złożoność przestrzeni dla średnich przypadków została przeanalizowana. Mówiąc dokładniej, jestem zainteresowany, aby dowiedzieć się, czy są jakieś problemy ze sprawdzoną dolną granicą złożoności przestrzeni, która jest superliniowa, a zwłaszcza, jeśli istnieją jakieś z analizą średnich przypadków (np. Granica jest zachowana, nawet jeśli algorytm jest dozwolony błądzić …
1
Zredukowanie podstawowych produktów faktoringowych do faktoringowych liczb całkowitych (w przeciętnym przypadku)
Moje pytanie dotyczy równoważności bezpieczeństwa różnych kandydujących funkcji jednokierunkowych, które można zbudować w oparciu o twardość faktoringu. Zakładając problem FAKTORING: [Biorąc pod uwagę dla losowych liczb pierwszych , znajdź , ]P , Q &lt; 2 n P QN.= PQN=PQN = PQP., Q &lt; 2nP,Q&lt;2nP, Q < 2^nP.PPQQQ funkcja nie może …
1
Niejednolici kontra Jednolici Przeciwnicy
To pytanie powstało w kontekście kryptografii, ale poniżej przedstawię je w kategoriach teorii złożoności, ponieważ ludzie tutaj są bardziej zaznajomieni z tym ostatnim. To pytanie dotyczy problemów w NP, ale nie w średniej P / poli i pokonania premii przez Oracle Access . Nieformalne oświadczenie: kiedy nierównomiernym przeciwnikom (tj. Wielorakiej …
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.