Właśnie przeczytałem na niemieckiej Wikipedii, że nieskończony wykres to wykres z nieskończoną liczbą węzłów lub nieskończoną liczbą krawędzi. Znam tylko aplikacje i algorytmy dla grafów skończonych. Do czego służą wykresy nieskończone? Jakie są ich zastosowania? Nie wyobrażam sobie algorytmów,...
Dwa powiązane pytania dotyczące obliczeń na ograniczonej głębokości: 1) Załóżmy, że zaczynasz od n bitów i na początku bitu i może wynosić 0 lub 1 z pewnym prawdopodobieństwem p (i), niezależnie. (Jeśli upraszcza to problem, możemy założyć, że wszystkie p (i) s wynoszą 0,1 lub 1/2.a nawet że...
Wykres liniowy hipergrafu jest (prostym) wykresem G mającym krawędzie H, ponieważ wierzchołki o dwóch krawędziach H sąsiadują w G, jeśli mają niepuste przecięcie. Hypergraph to r- hipergraph, jeśli każda jego krawędź ma co najwyżej r wierzchołków.HHHGGGHHHHHHGGGrrrrrr Jaka jest złożoność...
Chociaż twierdzenie Adlemana pokazuje, że , nie znam żadnej literatury badającej możliwe włączenie . Jakie konsekwencje teoretyczne pod względem złożoności miałoby takie włączenie?BPP⊆P/polyBPP⊆P/poly\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}BQP⊆P/polyBQP⊆P/poly\mathsf{BQP} \subseteq...
Niech będzie klasą wszystkich zwykłych języków.REGREG\mathsf{REG} Znane jest i . Ale czy istnieje jakaś charakterystyka języków w \ mathsf {AC} ^ 0 \ cap \ mathsf {REG} ?AC0⊄REGAC0⊄REG\mathsf{AC}^0 \not\subset \mathsf{REG}REG⊄AC0REG⊄AC0\mathsf{REG} \not\subset...
Załóżmy, że chcemy posortować listę z liczb rzeczywistych. Załóżmy, że otrzymujemy czarną skrzynkę, która może natychmiast posortować liczb rzeczywistych. Ile korzyści możemy zyskać dzięki tej czarnej skrzynce?S.SS √nnnn−−√n\sqrt n Na przykład, czy możemy posortować numery za pomocą tylko wywołań...
Biorąc pod uwagę określoną rodzinę podzbiorów uniwersum . Niech a my chcemy odpowiedzieć to .FF\mathcal{F}UUUS1,S2∈FS1,S2∈FS_1,S_2 \in \mathcal FS1⊆S2S1⊆S2S_1 \subseteq S_2 Szukam struktury danych, która pozwoli mi szybko odpowiedzieć na to pytanie. Moja aplikacja pochodzi z teorii grafów, w...
(To pytanie jest trochę „ankietą”). Aktualnie pracuję nad problemem, w którym próbuję podzielić krawędzie turnieju na dwa zestawy, z których oba są wymagane do spełnienia niektórych właściwości strukturalnych. Problem „czuje się” bardzo trudne, a ja w pełni się spodziewać, że będzie...
Dobrze wiadomo, że palindromy można rozpoznać w czasie liniowym na maszynach Turinga z taśmami, ale nie na maszynach Turinga z pojedynczą taśmą (w takim przypadku potrzebny czas jest kwadratowy). Algorytm czasu liniowego wykorzystuje kopię danych wejściowych, a zatem wykorzystuje również przestrzeń...
Pazur to . Trywialny algorytm wykryje pazur w czasie . Można to zrobić w , gdzie jest wykładnikiem szybkiego mnożenia macierzy, w następujący sposób: weź podrozdział wywołany przez dla każdego wierzchołka i znajdź trójkąt w jego uzupełnienie. O ( n 4 ) O ( n ω + 1 ) ω N [ v ]...
Biorąc pod uwagę wyrażenia regularne , czy istnieją jakieś nietrywialne granice wielkości najmniejszej kontekstowej gramatyki dla ?R1, … , RnR1,…,RnR_1, \dots, R_nR1∩ ⋯ ∩ RnR1∩⋯∩RnR_1 \cap \cdots \cap
Jak szybko niedeterministyczny algorytm dla problemu pełnego EXPTIME musiałby sugerować ? Algorytm niedeterministyczny czasu wielomianowego natychmiast implikowałby to, ponieważ ale nikt nie wierzy, że . Jeśli zrobiłem algebrę w prawo (patrz poniżej), twierdzenie o hierarchii czasu nadal dawałoby...
Czy istnieje typowany rachunek lambda, w którym odpowiednia logika w korespondencji Curry-Howarda jest spójna i gdzie istnieją możliwe do wpisania wyrażenia lambda dla każdej funkcji obliczeniowej? Jest to wprawdzie pytanie nieprecyzyjne, pozbawione precyzyjnej definicji „typowanego rachunku...
Mam dwa historyczne pytania: Kto pierwszy opisał obliczenia niedeterministyczne? Wiem, że Cook opisał problemy z NP-zupełnością i że Edmonds zaproponował, że algorytmy P są algorytmami „wydajnymi” lub „dobrymi”. Przeszukałem ten artykuł w Wikipedii i odszukałem „O złożoności obliczeniowej...
Powiedzmy, że język jest blisko P, jeśli istnieje algorytm wielomianowy, który poprawnie decyduje o na prawie wszystkich wejściach.LLLLLLL Innymi słowy, istnieje P , tak że zanika, co oznacza Oznacza to również, że przy jednolitym losowym danych wejściowych algorytm czasu policyjnego dla A da...
Wikipedia podaje przykłady problemów, w których liczenie wersji jest trudne, natomiast wersja decyzyjna jest łatwa. Niektóre z nich liczą doskonałe dopasowania, licząc liczbę rozwiązań SAT i liczbę sortowań topologicznych.222 Czy są jeszcze jakieś inne ważne klasy (powiedzmy przykłady z sieci,...
Pozornie bezcelowość wydobywania kryptowalut wywołała pytanie o przydatne alternatywy, zobacz te pytania na Bitcoin , CST , MO . Zastanawiam się, czy istnieje algorytm, który może przekonwertować praktycznie każde wyzwanie obliczeniowe doC\mathcal C (którego rozwiązanie można skutecznie...
Oznacz przez wnwnw_n liczbę słów o długości nnn w (możliwie niejednoznacznym) języku bezkontekstowym. Co wiadomo o wnwnw_n ? Jestem pewien, że dużo się tego badano, ale nie mogłem w ogóle nic
Recall liczba liczb pierwszych jest funkcją zliczania liczb pierwszych . Przez „PRIMES in P”, computing jest w #P. Czy problem # P jest kompletny? A może istnieje złożony powód, by sądzić, że ten problem nie jest # P-całkowity? π( n )π(n)\pi(n)≤ n≤n\le nπ( n )π(n)\pi(n) PS Zdaję sobie sprawę, że...
Dziś w Nowym Jorku i na całym świecie obchodzone są urodziny Christosa Papadimitriou. To dobra okazja, aby zapytać o relacje między klasą złożoności Christosa PPAD (i jego innymi klasami pokrewnymi) a komputerami kwantowymi. W swoim słynnym artykule z 1994 r. Papadimitriou wprowadził i...