Samoreferencyjność problemu P / NP była czasem podkreślana jako bariera dla jego rozwiązania, patrz na przykład artykuł Scotta Aaronsona, czy P vs. NP jest formalnie niezależny ? Jednym z wielu możliwych rozwiązań P / NP byłby dowód, że problem jest formalnie niezależny od ZFC lub prawdziwy, ale...
[Uwaga: uważam, że to pytanie w żaden sposób nie zależy od poprawności lub nieprawidłowości pracy Deolalikar.] Na blogu Scotta Aaronsona „ Shtetl Optimized” , w dyskusji na temat ostatniej próby Deolalikara przeciwko P vs NP, Leonid Gurvits skomentował : Próbowałem zrozumieć / przeformułować to...
Istnieje duża literatura na temat „testowania właściwości” - problemu polegającego na utworzeniu niewielkiej liczby zapytań do czarnej skrzynki do funkcji celu rozróżnienia dwóch przypadków:f:{0,1}n→Rf:{0,1}n→Rf\colon\{0,1\}^n \to R fff jest członkiem pewnej klasy funkcjiCC\mathcal{C} fff jest...
W przypadku niektórych algorytmów randomizowanych można go zdemandomizować, usuwając (przy możliwym koszcie w czasie wykonywania) użycie bitów losowych i maksymalizując pewną dolną granicę celu (zwykle obliczaną na podstawie faktu, że twierdzenia dotyczą oczekiwanej wydajności losowej algorytm)....
Języki liścia są pięknym sposobem na jednolite zdefiniowanie wielu klas złożoności. Większość klas złożoności jest zwykle określana przez model obliczeniowy (np. Deterministyczna / losowa TM) i związany z zasobami (czas dziennika, przestrzeń wielopunktowa itp.). Jednak w sformułowaniu języka liścia...
Czytając kilka ostatnich wątków na temat obliczeń kwantowych ( tutaj , tutaj i tutaj ), pamiętam interesujące pytanie o moc jakiegoś rodzaju maszyny do zachowania normalnego zachowania.ℓpℓp\ell_p Dla osób pracujących w teorii złożoności, które dążą do złożoności kwantowej, doskonałym tekstem...
Łańcuch dodatek jest ciągiem liczb naturalnych , gdzie x 1 = 1 , a każdy wskaźnik i ≥ 2 mamy x ı = x j + x k kilku wskaźników 1 ≤ j , k < i . Długość łańcucha addycji N ; docelowej sieci addycji x( x1, x2), … , Xn)(x1,x2,…,xn)(x_1, x_2, \dots, x_n)x1= 1x1=1x_1 = 1i ≥ 2i≥2i\ge 2xja= xjot+...
W artykule „A Compendium of Problems Complete for P” autorstwa Greenlawa, Hoovera i Ruzzo (PS) (PDF) znajduje się lista problemów w P, które nie są znane w NC i nie są znane jako P-complete . (Ta lista obejmuje wszystkie otwarte problemy w doskonałej ankiecie przeprowadzonej przez Karpa i...
Załóżmy, że mamy macierz n na n. Czy można zmienić kolejność wierszy i kolumn, tak aby uzyskać matrycę górnego trójkąta? To pytanie jest motywowane tym problemem: Pozytywne uporządkowanie topologiczne Pierwotny problem decyzyjny jest co najmniej tak trudny jak ten, więc wynik kompletności NP...
Niech f:{0,1}n→(2−n,1]f:{0,1}n→(2−n,1]f \colon \lbrace 0,1 \rbrace ^ n \to (2^{-n},1] będzie funkcją. Chcemy oszacować średnią fff ; to znaczy: E[f(n)]=2−n∑x∈{0,1}nf(x)E[f(n)]=2−n∑x∈{0,1}nf(x)\mathbb{E}[f(n)]=2^{-n}\sum_{x\in \lbrace 0,1 \rbrace ^ n}f(x) . NOTE: In the OP, the range of f was...
Immerman i Szelepcsenyi niezależnie okazało się, że . Stosując technikę zliczania indukcyjnego, Borodin i wsp. Udowodnili, że S A C i jest zamknięte pod komplementarnością dla i > 0 . Przed twierdzeniem Reingolda ( S L = L ) Nisan i Ta-Shma udowodnili S L = c o S L , stosując redukcje...
Używałem Junga ( http://jung.sourceforge.net/ ) do wizualizacji rangi strony i stwierdziłem, że jest trochę powolna i trudna do skalowania poza 100 węzłów. Zastanawiałem się, jakich innych narzędzi używają ludzie do analizy i wizualizacji sieci / sieci
Klasycznym problemem w teorii prawdopodobieństwa jest wyrażenie prawdopodobieństwa zdarzenia w kategoriach bardziej specyficznych zdarzeń. W najprostszym przypadku można powiedzieć . Write LET'S za zdarzenie .A B A ∩ BP[A∪B]=P[A]+P[B]−P[A∩B]P[A∪B]=P[A]+P[B]−P[A∩B]P[A \cup B] = P[A] + P[B] - P[A...
Załóżmy, że mamy problem sparametryzowany parametrem p o wartości rzeczywistej, który jest „łatwy” do rozwiązania, gdy i „twardy”, gdy p = p 1 dla niektórych wartości p 0 , p 1 .p = p0p=p0p=p_0p = p1p=p1p=p_1p0p0p_0p1p1p_1 Jednym z przykładów jest liczenie konfiguracji spinów na wykresach. Licząc...
Szukam dobrej ankiety na temat algorytmów i złożoności algebry liniowej (operacje takie jak rank, inverse, wartości własne, ... dla Boolean, oraz liczby całkowite / racjonalne) z naciskiem na równoległość ( hierarchia ) i algorytmy politime. Nie mogłem znaleźć ostatniego....
Większość prac jest teraz pisanych wspólnie, a współpracownicy często znajdują się w różnych miejscach. Zawsze używałem systemów kontroli wersji dla moich dokumentów i kodu, a także uważałem kontrolę wersji za kluczową dla wspólnych projektów oprogramowania, ale wydaje się, że wielu badaczy...
W klasie złożoności istnieją pewne domniemania, że NIE występują w klasie , tj. Problemy z deterministycznymi algorytmami równoległymi. Problem maksymalnego przepływu jest jednym z przykładów. I są problemy, WIĘCEJ, że są w , ale dowód jeszcze nie został znaleziony.N C N C.P.P\mathsf{P}N...
Powszechnie wiadomo, że potęgowanie modułowe (główna część operacji RSA) jest drogie obliczeniowo i, o ile rozumiem, preferowaną metodą jest potęgowanie modułowe Montgomery'ego . Modułowe potęgowanie jest również wyraźnie widoczne w algorytmie faktoringu kwantowego i tam również jest drogie. Więc:...
Tytuł mniej więcej mówi wszystko, ale myślę, że mógłbym dodać trochę tła i kilka konkretnych przykładów, którymi jestem zainteresowany. Teoretycy złożoności opisowej, tacy jak Immerman i Fagin, scharakteryzowali wiele najbardziej znanych klas złożoności za pomocą logiki. Na przykład NP można...
Czy przeprowadzono badania nad implementacją konstrukcji ekstraktorów losowości? Wydaje się, że proofy ekstraktora wykorzystują Big-Oh, pozostawiając możliwość dużych, ukrytych stałych, czyniąc implementacje programowe potencjalnie nierealnymi. Trochę kontekstu: jestem zainteresowany...