Ostatnio zastanawiałem się nad wprowadzeniem do algorytmów holograficznych. Natknąłem się na obiekty kombinatoryczne zwane Pfaffians. W tej chwili tak naprawdę niewiele o nich wiem i natknąłem się na zaskakujące zastosowania, które można zastosować. Na przykład dowiedziałem się, że można ich...
Osłonę wierzchołka można łatwo zredukować do zestawu niezależnego i odwrotnie. Jednak w kontekście sparametryzowanej złożoności zestaw niezależny jest trudniejszy niż osłona wierzchołka. Jądro z wierzchołków istnieje problem pokrycia wierzchołkowego, ale niezależnego zestawu jest biała 1...
Zakładając, że NP! = CoNP, to nie ma certyfikatu wielomianu dla problemu pełnego coNP. Ale co z podwykładniczym certyfikatem wielkości? Czy w szczególności w przypadku coSAT istnieje podwykładniczy dowód wielkości, aby udowodnić, że formuła jest niezadowalająca? Jeśli nie, jakie są negatywne...
To, co nazywam liczeniem, to problem polegający na znalezieniu liczby rozwiązań funkcji. Dokładniej, biorąc pod uwagę funkcję fa: N→ { 0 , 1 }f:N→{0,1}f:N\to \{0,1\} (niekoniecznie czarna skrzynka), przybliżone # { x ∈ N∣ f( x ) = 1 } = | fa- 1( 1 ) |#{x∈N∣f(x)=1}=|f−1(1)|\#\{x\in N\mid f(x)= 1\}=...
Powszechnie wiadomo, że złożoność odróżnianie się stronniczy monetę z jednego sprawiedliwego jest θ ( ε - 2 ) . Czy istnieją wyniki dla odróżnienia monety p od monety p + ϵ ? Widzę, że dla specjalnego przypadku p = 0 złożoność będzie wynosić ϵ - 1 . Mam przeczucie, że złożoność będzie zależeć od...
P / poly to klasa problemów decyzyjnych rozwiązanych przez rodzinę obwodów boolowskich wielkości wielomianowych. Alternatywnie można go zdefiniować jako wielomianową maszynę Turinga, która otrzymuje ciąg porady, który jest wielomianem wielkości w n, i który opiera się wyłącznie na rozmiarze n. mP...
Czy znasz jakieś problemy (najlepiej przynajmniej nieco dobrze znane), w których dla praktycznego rozmiaru problemu algorytm wykładniczy działa znacznie szybciej niż najbardziej znany odpowiednik czasu wielomianowego. Załóżmy na przykład, że problem ma praktyczny rozmiar * i istnieją dwa znane...
Biorąc pod uwagę algorytm działający w czasie , możemy go przekształcić w „trywialną” rodzinę obwodów jednorodnych dla tego samego problemu wielkości co najwyżej ≈ t ( n ) log t ( n ) .t ( n )t(n)t(n)≈ t ( n ) logt ( n )≈t(n)logt(n)\approx t(n)\log t(n) Z drugiej strony może się zdarzyć, że mamy...
Istnieje wiele dobrze znanych C 0 wielkości obwód dolny związanego wyniki w oparciu o losowe ograniczeń i przełączania lematu .AC0AC0\mathsf{AC^0} Czy możemy opracować wynik zamiany lematu, aby udowodnić niższą wielkość dla obwodów TC0TC0\mathsf{TC^0} (podobnie do dolnej granicy dla...
W swoim kluczowym artykule Teoretyczne algorytmy grupowania macierzy Cohn, Kleinberg, Szegedy i Umans przedstawiają koncepcję unikatowej układanki (zdefiniowanej poniżej) i zdolności USP. Twierdzą oni, że Coppersmith i Winograd, w ich własnym papierze przełomowy Mnożenie macierzy poprzez ciąg...
Adleman wykazały w 1978 r : Jeżeli logiczna funkcja o zmiennych może być obliczany za pomocą prawdopodobieństwa logicznego obwodu o rozmiarze , a następnie może być obliczany za pomocą deterministycznych obwód boolowski wielomianu wielkości w i ; właściwie o wielkości ....
Eliminacja Gaussa sprawia, że wyznacznik macierzy obliczany jest w czasie wielomianowym. Zmniejszenie złożoności obliczania wyznacznika, które w przeciwnym razie jest sumą terminów wykładniczych, wynika z obecności alternatywnych znaków ujemnych (których brak sprawia, że obliczenia są trwałe,...
Najmniejsza znana formuła dla wyznacznika ma rozmiar zgodnie z folklorem (lub Ran Raz w swoim artykule Wieloliniowe formuły na stałe i determinant mają rozmiar wielobiegowy ).nO (logn )nO(logn)n^{\mathcal O(\log n)} Czy masz na to jakieś odniesienia? W szczególności, czym jest ta...
Algorytm testowania dystrybucji dla właściwości dystrybucji P (która jest tylko pewnym podzbiorem wszystkich dystrybucji w ciągu [n]) ma dostęp do próbek zgodnie z pewną dystrybucją D i jest zobowiązany do podjęcia decyzji (whp), czy lub d ( D , P ) > ϵ ( d tutaj jest zwykle odległością ℓ 1 )....
Niech będzie funkcją boolowską zmiennych boolowskich. Niech będzie oczekiwaną wartością gdy jest uzyskane z poprzez odwrócenie każdej współrzędnej z prawdopodobieństwem .n g ( x ) = T ϵ ( f ) ( x ) f ( y ) y x ϵ / 2faffnnnsol( x ) = Tϵ( f) ( x )g(x)=Tϵ(f)(x)g(x)=T_\epsilon (f) (x)fa(...
Niech będzie funkcją większościową, tj. F ( x ) = 1 wtedy i tylko wtedy, gdy ∑ n i = 1 x i > n / 2 . Zastanawiałem się, czy istnieje prosty dowód na następujący fakt (przez „prosty” mam na myśli to, że nie polegałem na metodzie probabilistycznej, jak Valiant 84, ani na sieciach sortujących;...
W swojej książce Computational Complexity Papadimitriou definiuje FNP w następujący sposób: Załóżmy, że jest językiem w NP . Propozycja według 9.1 jest rozstrzygalne wielomianowego razem wielomianowo zrównoważony stosunek R L takie, że dla wszystkich ciągów x : jest łańcuch Y z R L ( x , y ) ,...
Mówimy, że funkcja jest konstruowalna w czasie , jeśli istnieje deterministyczna wielopasmowa maszyna Turinga M, która na wszystkich wejściach długości n wykonuje co najwyżej f ( n ) kroki i dla każdego n istnieje pewien wkład długość n, na której M wykonuje dokładnie f ( n ) kroki.fa: N →...
Przypomnijmy, że szerokość o rozdzielczości odrzucenia o wzorze CNF jest maksymalna liczba literałach w klauzuli występującego w . Dla każdego istnieją niezadowalające wzory w 3-CNF st. Każde odrzucenie rozdzielczości wymaga szerokości co najmniej .F.RRRfaFFw F F wRRRwwwfaFFfaFFwww Potrzebuję...
Wiemy, że problem zliczania liczby spełniających przypisanie w danej ogólnej formule boolowskiej (CNF-SAT), danej formule DNF, a nawet danej formule 2SAT jest problemem # P-zupełnym . Teraz rozważmy CNF-SAT bez literału ujemnego (no , zawsze ). Problem decyzyjny jest bardzo łatwy (ustaw wszystkie...