Pytania otagowane jako cc.complexity-theory

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

1
Klasy złożoności obwodów liniowych
Klasa to funkcje klasy obliczalne przez rodziny obwodów ograniczonego wielkości i głębokości . -hierarchy jest sumą tych klas.NCjaNCi\textrm{NC}^inO ( 1 )nO(1)n^{O(1)}O ( logja( n ) )O(logi⁡(n))O(\log^i(n))NCNC\textrm{NC} Czy jest jakieś badanie wariantu wielkości hierarchicznej tej hierarchii? Czy to rodziny obwodów ograniczonego wachlarza, głębokości polilogu i rozmiaru liniowego? Wiem, że istnieje trochę …
1
Jaka jest złożoność tej gry?
To jest uogólnienie mojego poprzedniego pytania . Niech będzie wielomianem czasie deterministyczny urządzenie, które może zadać pytania do jakiegoś oracle . Początkowo jest puste, ale można to zmienić po grze, która zostanie opisana poniżej. Niech będzie ciągiem znaków.MMMAAAAAAxxx Rozważ następującą grę Alice and Bob. Początkowo Alice i Bob mają odpowiednio …
1
Szybka klasyczna symulacja algorytmów kwantowych
Czy istnieją przykłady przypadków, w których klasyczna symulacja algorytmu kwantowego dla problemu przewyższa najlepiej znany wcześniej klasyczny algorytm dla tego problemu? „Lepsze wyniki” nie musi oznaczać innej klasy złożoności, może po prostu być lepsze skalowanie. To pytanie zostało zainspirowane przypadkiem wydajnej klasycznej symulacji kwantowego algorytmu rekomendacji .
1
Czy ta gra jest EXPSPACE?
Niech będzie wielomianem czasie deterministyczny urządzenie, które może zadać pytania do jakiegoś oracle A . Początkowo A jest puste, ale można to zmienić po grze, która zostanie opisana poniżej. Niech x będzie ciągiem znaków.M.MMZAAAZAAAxxx Rozważ następującą grę Alice and Bob. Początkowo Alice i Bob mają odpowiednio i m B dolarów. …
2
Powszechny wgląd w hipotetyczną złożoność problemów graficznych
Natknąłem się na dwa przykłady hipotetycznej twardości niektórych problemów graficznych. Hipotetyczna twardość oznacza, że ​​obalenie niektórych przypuszczeń oznaczałoby zupełność NP odpowiedniego problemu grafowego. Na przykład, hipoteza Barnette'a stwierdza, że ​​każdy 3-połączony sześcienny dwuwymiarowy wykres jest hamiltonianem. Feder i Subi udowodnili, że obalenie przypuszczenia oznaczałoby zupełność NP problemu cyklu hamiltonowskiego na …
1
Na rzadkich kompletach i P vs L.
Twierdzenie Mahaneya mówi nam, że jeśli istnieje rzadki zestaw przy wielomianowych redukcjach wielokrotności jeden, to . (Patrz „ Rzadkie kompletne zestawy dla NP: Rozwiązanie przypuszczenia Bermana i Hartmanisa ”)NPNPNPP=NPP=NPP = NP Czy znane są konsekwencje istnienia rzadkich kompletnych zestawów dla innych klas złożoności? W szczególności, jeśli w obszarze logarytmicznym występuje …
1
Decydowanie o najbardziej znaczącym mnożeniu binarnym
Interesuje mnie określenie złożoności następującego problemu decyzyjnego: Biorąc pod uwagę dwie liczby całkowite i l 2 (każda z co najwyżej m bitami), zdecyduj, czy najbardziej znaczącym bitem z mnożenia l 1 ⋅ l 2 jest 1 (gdzie wynik jest drukowany w 2-bitowych bitach z możliwymi początkowymi zerami)?l1l1l_1l2)l2l_2l1⋅ l2)l1⋅l2l_1 \cdot l_2 …
1
Sortowanie ze średnią porównań
Czy istnieje algorytm sortowania oparty na porównaniu, który wykorzystuje średnie porównania ?lg(n!)+o(n)lg(n!)+o(n)\mathrm{lg}(n!)+o(n) Istnienie algorytmu porównania najgorszego przypadku jest otwartym problemem, ale średni przypadek wystarcza dla algorytmu losowego z oczekiwanym porównania dla każdego wkładu. Znaczenie polega na tym, że są to porównania o (n) z optymalnych, marnując średnio tylko o (1) …
2
Złożoność homogenizacji łańcucha
Motywacja : Opracowując narzędzia do wersjonowania danych, zaczęliśmy szukać algorytmów do „różnicowania” dwóch zestawów liczb całkowitych, wymyślając sekwencję przekształceń, które przenoszą jeden zestaw liczb całkowitych na drugi. Udało nam się zredukować ten problem do następującego bardzo naturalnego problemu, który wydaje się mieć połączenia do edycji odległości, grupowania przez zamianę i …
1
Czy SAT w ograniczonej szerokości jest rozstrzygalny w przestrzeni logów?
Elberfeld, Jakoby i Tantau 2010 ( ECCC TR10-062 ) dowiodły, że zajmująca mało miejsca wersja twierdzenia Bodlaendera. Wykazali, że w przypadku wykresów o szerokości co najwyżej rozkład drzewa o szerokości k można znaleźć za pomocą przestrzeni logarytmicznej. Stały współczynnik w ograniczonej przestrzeni zależy od k . (Twierdzenie Bodlaendera pokazuje liniowe …
1
Kiedy BPP z tendencyjną monetą równa się standardowemu BPP?
Pozwól probabilistycznej maszynie Turinga mieć dostęp do nieuczciwej monety, która pojawia się z prawdopodobieństwem (trzepnięcia są niezależne). Zdefiniuj jako klasę języków rozpoznawalnych przez taki komputer w czasie wielomianowym. Standardowym ćwiczeniem jest wykazanie, że:B P P ppppBPPpBPPpBPP_p A) Jeśli jest racjonalne lub nawet obliczalne z to . (Przy -computable to znaczy: …
1
Złożoność osiągalności w liniowych układach dynamicznych nad polami skończonymi
Niech AAA będzie macierzą nad polem skończonym F2={0,1}F2={0,1}\mathbb{F}_2 = \{0,1\} a xxx , yyy będą wektorami przestrzeni Fn2F2n\mathbb{F}_2^n . Interesuje mnie złożoność obliczeniowa przy podejmowaniu decyzji, czy istnieje t∈Nt∈Nt \in \mathbb{N} takie, że Atx=yAtx=yA^t x = y , tj. Problem osiągalności liniowych układów dynamicznych nad polami skończonymi. Problem ten jest …
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.