Jest to kontynuacja ostatniego pytania zadanego przez A. Pala: Rozwiązywanie programów półfinałowych w czasie wielomianowym . Nadal zastanawiam się nad faktycznym czasem działania algorytmów obliczających rozwiązanie programu półfinałowego (SDP). Jak zauważył Robin w swoim komentarzu do powyższego...
Czy są jakieś przypuszczenia w informatyce teoretycznej, które dotyczą jakiegoś parametru n i zostały udowodnione dla małych wartości n AND dla liczb pierwszych, ale później okazały się fałszywe? W teorii liczb takie problemy istnieją, np. jak wskazuje Aaron Meyerowitz na temat współczynników...
Jestem studentem matematyki z solidnym doświadczeniem w logice. Wziąłem roczny kurs magisterski z logiki wraz z kursami absolwentów teorii modeli skończonych, a także teorii wymuszania i teorii mnożenia. Większość tekstów CS wydaje się przyjmować jedynie bardzo skromne tło logiki, które w...
Każda monada jest również funktorem aplikacyjnym, a każdy funktor aplikacyjny jest funktorem. Ponadto każdy comonad jest funktorem. Czy istnieje podobna koncepcja między comonadami i funktorami, coś w rodzaju funktora kooperacyjnego i jakie są jego
Rozważ permutację σσ\sigma wynoszącą [ 1 .. n ][1 ..n][1..n] . Inwersję definiuje się jako parę ( i , j )(ja,jot)(i, j) indeksów takich, że ja < jja<joti < j i σ( i ) > σ( j )σ(ja)>σ(jot)\sigma(i) > \sigma(j) . Zdefiniuj ZAkZAkA_k jako liczbę permutacji [ 1 .. n ][1 ..n][1..n] z co...
Złożoność obwodu złożoności jest jednym z głównych obszarów badań w ramach teorii złożoności obwodu. Ten temat ma swoje początki w wynikach takich jak „funkcja parzystości nie jest w ” i „funkcja mod nie jest obliczana przez ”, gdzie jest klasą języków rozstrzygalnych na podstawie niejednolitej,...
W algorytmie Strassena, aby obliczyć iloczyn dwóch macierzy ZAZA\mathbf{A} i , macierze i są podzielone na macierze blokowe i algorytm kontynuuje rekurencyjne obliczanie bloków produkty matryca-matryca w przeciwieństwie do naiwnych blokowych produktów matrycowo-matrycowych, tj. jeśli chcemy ,...
Szukam naturalnych przykładów wydajnych algorytmów (tj. W czasie wielomianowym) ul ich poprawność i skuteczność można konstruktywnie udowodnić (np. w lub ), alePRAPRAPRAHAHAHA nie jest znany żaden dowód wykorzystujący tylko wydajne koncepcje (tzn. nie wiemy, jak udowodnić ich poprawność i...
Począwszy od Curry-Howarda-Lambka, pojawiła się niezła trójca typów teorii, logiki i kategorii. Jestem ciekawy, jaką semantyczną kategorię uzyskujesz, gdy dodajesz (przymus) podtyp do teorii typów - wygląda na to, że nie zostało to zbytnio zbadane, jeśli w ogóle. Ogólnie rzecz biorąc, dodanie...
Ostatnio spotkałem następujący wariant kolorowania krawędzi. Biorąc pod uwagę połączony niekierowany wykres, znajdź kolorystykę krawędzi, która wykorzystuje maksymalną liczbę kolorów, jednocześnie spełniając ograniczenie, że dla każdego wierzchołka krawędzie padające na v używają co najwyżej...
Jedną rzeczą, którą komputery kwantowe mogą zrobić (być może nawet z tylko BPP + obwody kwantowe głębokości logarytmicznej), jest przybliżenie próbki transformaty Fouriera funkcji logicznej wartościowej w P.±1±1\pm 1 Tutaj i poniżej, kiedy mówię o próbkowaniu transformaty Fouriera, mam na myśli...
Rozważmy następujący problemQQQ : Otrzymujemy liczbę całkowitą i przedziałów z . także liczb całkowitych . Zadanie polega na wybraniu minimalnej liczby przedziałównnnkkk[li,ri][li,ri][l_i,r_i]1≤li≤ri≤2n1≤li≤ri≤2n1\leq l_i\leq r_i\leq 2n2n2n2nd1,…,d2n≥0d1,…,d2n≥0d_1,…,d_{2n}\geq 0 , że dla każdego i...
Czy próbując przekonać ekonomistów o znaczeniu teorii złożoności w druku, istnieje standardowe odniesienie do cytowania? Znam post na blogu Noama Nisana , ankietę Tima Roughgarden i rozdział 11 eseju Scotta Aaronsona . Te posty są dostępne dla informatyków, ale nie używają języka ekonomistów i nie...
Czy w literaturze znana jest następująca klasa grafów? Klasa wykresów parametryzowany dodatnimi liczbami całkowitymi i T i zawiera co wykres G = ( V , E ), tak, że dla każdego wierzchołka v ∈ V The podgrafu z G wywołane na wszystkich wierzchołków w odległości co najwyżej d z V w G ma szerokość co...
Robię przegląd literatury na temat problemu izomorfizmu grafów. Większość artykułów, które czytam, są napisane przez EM Luksa i Laszlo Babai. W tych pracach wykorzystano znajomość teorii grup i teorii złożoności na wysokim poziomie. Ponieważ jestem nowy w tej dziedzinie, wiele rzeczy nie jest dla...
Obecnie jestem uczniem szkoły średniej, interesuję się informatyką teoretyczną i matematyką stosowaną. Nauczyłem się algebry liniowej, rachunku różniczkowego i matematycznego. Mam naiwne przekonanie, że aby pisać lepsze algorytmy, trzeba znać tyle matematyki, ile się da, ponieważ można się uczyć o...
Część pracy nad czułością w porównaniu do czułości bloku miała na celu zbadanie funkcji z możliwie największą luką między s(f)s(f)s(f) i bs(f)bs(f)bs(f) w celu rozstrzygnięcia przypuszczenia, że bs(f)bs(f)bs(f) jest tylko wielomianowo większy niż s(f)s(f)s(f) . Co z przeciwnym kierunkiem? Co...
Załóżmy, że rozważam następujący wariant BPP, który pozwala nam nazywać się E (xact) BPP: Język jest w EBPP, jeśli istnieje wielomianowy losowy czas TG, który akceptuje każde słowo z prawdopodobieństwem dokładnie 3/4 i każde słowo nie w język z prawdopodobieństwem dokładnie 1/4. Oczywiście EBPP...
Podczas przeszukiwania Systemu informacji o klasach grafów i ich inkluzjach znalazłem kilka klas grafów, dla których problem cyklu Hamiltoniana jest NP-kompletny, natomiast złożoność problemów ścieżki Hamiltonian NIE jest znana. Niektóre z tych klas to dwuczęściowe wykresy o maksymalnym stopniu 3,...
Zgodnie z sugestią Josha Grochowa przekształcam swój komentarz z poprzedniego pytania w nowe pytanie. Jakie mamy dowody na ?UP≠NPUP≠NP\mathsf{UP} \neq \mathsf{NP} Tutaj to klasa języków rozpoznawalnych przez niedeterministyczne maszyny Turinga o wielomianowym czasie, które mają unikalną...