Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

2
Które parametry wykresu NIE są skoncentrowane na losowych wykresach?
Dobrze wiadomo, że wiele ważnych parametrów wykresu pokazuje (silne) stężenie na losowych wykresach, przynajmniej w pewnym zakresie prawdopodobieństwa krawędzi. Niektóre typowe przykłady to liczba chromatyczna, maksymalna klika, maksymalna niezależny zestaw maksymalne dopasowanie, numer dominacja, liczba kopii stałe podgrafu, średnicy, maksymalny stopień, numer Choice (lista kolorowania numer), Lovász θθ\theta -liczba, szerokość …
2
Pytanie o dwie matryce: Hadamard przeciwko „magicznej” w dowodzie przypuszczenia wrażliwości
Najnowszy i niezwykle zręczny dowód domniemania wrażliwości opiera się na wyraźnej * konstrukcji macierzy An∈{−1,0,1}2n×2nAn∈{−1,0,1}2n×2nA_n\in\{-1,0,1\}^{2^n\times 2^n} , zdefiniowanej rekurencyjnie w następujący sposób: A1=(0110)A1=(0110)A_1 = \begin{pmatrix} 0&1\\1&0\end{pmatrix} oraz dla n≥2n≥2n\geq 2 , n = ( n - 1 mi n - 1 mi n - 1An=(An−1In−1In−1−An−1)An=(An−1In−1In−1−An−1)A_{n} = \begin{pmatrix} A_{n-1}&I_{n-1}\\I_{n-1}&-A_{n-1}\end{pmatrix} W szczególności …
1
Czy nadal jest możliwe określenie złożoności obliczania szerokości wykresów płaskich?
Dla stałej można określić w czasie liniowym, biorąc pod uwagę wykres wejściowy G , czy jego szerokość wynosi ≤ k . Jednakże, gdy zarówno k jak i G są podane jako dane wejściowe, problem jest trudny NP. ( Źródło ).k∈Nk∈Nk \in \mathbb{N}GGG≤k≤k\leq kkkkGGG Jednak gdy wykres wejściowy jest płaski , …
2
Czy Cheeger jest stały -trwały?
Przeczytałem w niezliczonych artykułach, że wyznaczanie stałej Cheegera na wykresie to -hard. To wydaje się być twierdzeniem ludowym, ale nigdy nie znalazłem ani cytatu, ani dowodu na to stwierdzenie. Komu mam to przypisać? W starym artykule (Isoperimetric Numbers of Graphs, J. Comb. Theory B, 1989) Mohar potwierdza to twierdzenie „dla …
3
Jakie są relacje między tymi hipotezami w teorii drobnoziarnistej złożoności?
Teoria złożoności, poprzez takie koncepcje jak kompletność NP, rozróżnia problemy obliczeniowe, które mają względnie skuteczne rozwiązania, i te, które są trudne do rozwiązania. Złożoność „drobnoziarnista” ma na celu dopracowanie tego jakościowego rozróżnienia w ilościowy przewodnik co do dokładnego czasu potrzebnego na rozwiązanie problemów. Więcej informacji można znaleźć tutaj: http://simons.berkeley.edu/programs/complexity2015 Oto …
1
Decydowanie o pustce przecięcia zwykłych języków w czasie subkwadratowym
Niech będą dwoma zwykłymi językami podanymi przez NFA M_1 jako dane wejściowe.M 1 , M 2L.1, L2)L1,L2L_1,L_2M.1, M2)M1,M2M_1,M_2 Załóżmy, że chcielibyśmy sprawdzić, czy . Można to wyraźnie zrobić za pomocą algorytmu kwadratowego, który oblicza automat produktu , , ale zastanawiałem się, czy wiadomo coś bardziej wydajnego.M 1 , M 2L.1∩ …
2
Rozpoznawanie węzłów jako dowód pracy
Obecnie bitcoin ma system proof of work (PoW) wykorzystujący SHA256. Inne funkcje skrótu wykorzystują wykresy wykorzystania systemu dowodu pracy, częściowe odwrócenie funkcji skrótu. Czy można zastosować problem decyzyjny w teorii węzłów, taki jak rozpoznawanie węzłów, i uczynić z niego funkcję dowodu pracy? Czy ktoś już to zrobił? Ponadto, kiedy będziemy …
1
Losowa złożoność zapytań problemu drzew połączonych
Ważny artykuł z 2003 roku autorstwa Childsa i in.wprowadził „problem drzew połączonych”: problem dopuszczający wykładnicze przyspieszenie kwantowe, który nie jest podobny do żadnego innego znanego nam problemu. W tym problemie otrzymaliśmy wykładniczo duży wykres, taki jak ten pokazany poniżej, który składa się z dwóch kompletnych dwójkowych drzewek głębokości n, których …
3
Reprezentowanie OR za pomocą wielomianów
Wiem, że w trywialny sposób funkcja OR dla zmiennych może być dokładnie reprezentowana przez wielomian jako taki: , czyli stopnia .nnnx1,…,xnx1,…,xnx_1,\ldots, x_np(x1,…,xn)p(x1,…,xn)p(x_1,\ldots,x_n)p(x1,…,xn)=1−∏ni=1(1−xi)p(x1,…,xn)=1−∏i=1n(1−xi)p(x_1,\ldots,x_n) = 1-\prod_{i = 1}^n\left(1-x_i\right)nnn Ale jak mogę pokazać, co wydaje się oczywiste, że jeśli jest wielomianem, który dokładnie reprezentuje funkcję OR (więc ), a następnie ?∀ x ∈ …
5
Problemy z EXPSPACE
Obecnie próbuję znaleźć problemy pełne EXPSPACE (głównie w celu znalezienia inspiracji do redukcji) i jestem zaskoczony małą liczbą nadchodzących wyników. Jak dotąd je znalazłem i mam problem z rozwinięciem listy: uniwersalność (lub inne właściwości) wyrażeń regularnych z potęgowaniem. problemy związane z systemami dodawania wektorów nieobserwowalne gry (patrz na przykład ten …
1
Pobieranie próbek zadowalających wzorów 3-SAT
Rozważ następujące zadanie obliczeniowe: Chcemy pobrać próbkę 3-SAT formuły zmiennych (wariant: zmiennych klauzule m ) w odniesieniu do równomiernego rozkładu prawdopodobieństwa, pod warunkiem spełnienia wzoru:nnnnnnmmm P1: Czy można to skutecznie osiągnąć za pomocą klasycznego komputera (z losowymi bitami)? P2: Czy można to skutecznie osiągnąć za pomocą komputera kwantowego? Interesują mnie …
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.