Pytania otagowane jako cc.complexity-theory

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

1
Złożoność obliczeniowa mnożenia macierzy
Szukam informacji o złożoności obliczeniowej mnożenia macierzy prostokątnych macierzy. Wikipedia stwierdza, że ​​złożoność pomnożenia przez B ∈ R n × p wynosi O ( m n p ) (mnożenie podręcznika).A∈Rm×nA∈Rm×nA \in \mathbb{R}^{m \times n}B∈Rn×pB∈Rn×pB \in \mathbb{R}^{n \times p}O(mnp)O(mnp)O(mnp) Mam przypadek, w którym i n są znacznie mniejsze niż p , …
1
Najlepsza złożoność zapytań algorytmu uczenia się Goldreich-Levin / Kushilevitz-Mansour
Jaka jest najbardziej znana złożoność zapytań algorytmu uczenia się Goldreich-Levin? Notatki z bloga Luca Trevisan , Lemma 3, stwierdza się jako . Czy jest to najlepiej znane pod względem zależności od n ? Będę szczególnie wdzięczny za odniesienie do źródła cytowanego!O ( 1 / ϵ4n logn )O(1/ϵ4nlog⁡n)O(1/\epsilon^4 n \log n)nnn …
2
Złożoność optymalizacji w stosunku do grupy jednolitej
Jaka jest złożoność obliczeniowa optymalizacji różnych funkcji w grupie jednolitej ?U(n)U(n)\mathcal{U}(n) Typowe zadanie, często wynikające z teorii informacji kwantowej byłoby maksymalizując ilość typu (lub wyższych wielomiany rzędu w U ) w stosunku do wszystkich macierze jednostkowe U . Czy tego rodzaju optymalizacja jest wydajna (być może w przybliżeniu) do obliczenia, …
1
Wczesna historia niektórych wyników kompromisów czasoprzestrzennych?
Interesuje mnie wczesna historia opublikowanych wyników dotyczących kompromisów czasoprzestrzennych ogólnego przeznaczenia. W szczególności chcę wiedzieć, kto jako pierwszy opisał następujący typ algorytmu do oceny obliczeń posiadających dowolny wykres przepływu danych z O-stopniem (1), wykorzystujący przestrzeń proporcjonalną do głębokości (nie szerokości) wykresu przepływu danych (plus rozmiar danych wejściowych), wykonując prostą pierwszą …
3
Czy P zawiera języki, których istnienie jest niezależne od PA lub ZFC? (Wiki społeczności TCS)
Odpowiedź: nieznana. Zadawane pytania są naturalne, otwarte i pozornie trudne; pytanie jest teraz wiki społeczności. Przegląd Pytanie ma na celu podzielenie języków należących do klasy złożoności - wraz z maszynami decyzyjnymi Turinga (TM), które akceptują te języki - na dwie uzupełniające się podklasy:PPP języki gnostyczne i bazy TM (które można …
1
Na złożoność minimalizacji przepustowości
Problem przepustowości wykresu jest zdefiniowany następująco. Biorąc pod uwagę wykres G=(V,E)G=(V,E)G=(V,E) , A układ fff z jest mapowanie jeden do jednego z wierzchołków na całkowite . Pasma określa się jakoG { 1 , … , | V | } fGGGGGG{1,…,|V|}{1,…,|V|}\{1, \ldots, |V|\}fff bw(f)=max{|f(u)−f(v)|∣{u,v}∈E}bw(f)=max{|f(u)−f(v)|∣{u,v}∈E}bw(f) = \max \{|f(u) - f(v)| \mid \{u,v\} …
2
Pytanie do # P-kompletnego dowodu stałego z Ben-Dor / Halevi
W pracy Ben-Dor / Halevi [1] podano kolejny dowód na to, że stały jest -kompletny. W dalszej części artykułu pokazano łańcuch redukcji IntPerm ∝ NoNegPerm ∝ 2PowersPerm ∝ 0/1-Perm, podczas gdy wartość stała jest zachowana wzdłuż łańcucha. Ponieważ liczba satysfakcjonujących przypisań wzoru 3SAT Φ#P#P\#PIntPerm∝NoNegPerm∝2PowersPerm∝0/1-PermIntPerm∝NoNegPerm∝2PowersPerm∝0/1-Perm\begin{equation} \text{IntPerm} \propto \text{NoNegPerm} \propto \text{2PowersPerm} \propto …
1
Redukcja przestrzeni logów z obwodów Parity-L na obwody CNOT?
Pytanie. W swoim artykule Ulepszona symulacja obwodów stabilizatora , Aaronson i Gottesman twierdzą, że symulacja obwodu CNOT jest zakończona w ⊕L (przy zmniejszeniu przestrzeni logarytmicznej). Oczywiste jest, że jest on zawarty w ⊕L ; jak zachowuje się wynik twardości? Równoważnie: czy występuje ograniczenie przestrzeni logicznej z iterowanych produktów macierzy modulo …
1
kontra
Wiem, że PNP[logn]PNP[log⁡n]\mathsf{P}^{\mathsf{NP}[\log n]} (logarytmicznie wiele wywołań do NP oracle) jest równoważne PNP||PNP||\mathsf{P}^{\mathsf{NP}||}(wielomianowa liczba równoległych zapytań do NP oracle). Zastanawiałem się, czy wersja „funkcyjna” tych klas również jest równoważna, to znaczy czy Jeśli wiadomo, że to prawda, wskaźnik byłby naprawdę pomocny.FPNP[logn]=FPNP||FPNP[log⁡n]=FPNP|| \mathsf{FP}^{\mathsf{NP}[\log n]} = \mathsf{FP}^{\mathsf{NP}||}
3
Teoria złożoności, gdy wyrocznia jest częścią danych wejściowych
Najczęstszy sposób, w jaki wyrocznie występują w teorii złożoności, jest następujący: Stała wyrocznia jest udostępniana, powiedzmy, maszynie Turinga z pewnymi ograniczonymi zasobami, i jedna bada, w jaki sposób wyrocznia zwiększa moc obliczeniową maszyny. Istnieje jednak inny sposób, w jaki czasami zdarzają się wyrocznie: jako część danych wejściowych . Załóżmy na …
3
Jak mogę pokazać, że problem Gap-P jest poza #P
Istnieje wiele problemów w kombinatorycznej teorii reprezentacji i geometrii algebraicznej, dla których nie jest znana formuła dodatnia. Myślę o kilku przykładach, ale pozwólcie, że obliczę współczynniki Kroneckera jako mój przykład. Zwykle pojęcie „formuły dodatniej” nie jest precyzyjnie zdefiniowane w kombinatorykach, ale z grubsza oznacza „opis jako liczność zbioru rozsądnie wyraźnego”. …
1
Co wiadomo na temat interaktywnych proofów z wieloma dowodami z krótkimi wiadomościami?
Beigi, Shor i Watrous mają bardzo ładny artykuł na temat mocy kwantowych dowodów interaktywnych z krótkimi wiadomościami. Rozważają trzy warianty „krótkich wiadomości”, a konkretny, na którym mi zależy, to ich drugi wariant, w którym można wysłać dowolną liczbę wiadomości, ale całkowita długość wiadomości musi być logarytmiczna. W szczególności pokazują, że …
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.