To pytanie jest motywowane pytaniem MathOverflow Peng Zhanga . Valiant wykazał, że zliczanie maksymalnych klików na wykresie ogólnym jest zakończone metodą # P, ale co jeśli ograniczymy się do wykresów nieporównywalności (tzn. Chcemy policzyć maksymalne antichains w skończonym zestawie)? To pytanie...
Parzystość-L, znana również jako , jest zestawem języków rozpoznawanych przez niedeterministyczną maszynę Turinga, która może rozróżniać tylko liczbę parzystą lub nieparzystą liczby ścieżek „akceptacji”. Ostatnie powiązane pytanie zadał Niel de Beaudrap.⊕⊕\oplus Moje pytanie jest następujące:...
Niech kwadratowa rzeczywista macierz A i dwa wektory x i b o długości n , takie, że A x = b . Rozwiązanie x poprzez standardową eliminację Gaussa daje łączną złożoność prawie O ( n 3 ) . Są jednak przypadki, w których rozwiązywanie (lub ϵ - rozwiązywanie w przybliżeniu) dla x kosztuje O ( n log ρ...
W definicji (silnej) ciągliwości parametrów stałych ustalony czas jest wyrażeniem postaci gdzie instancja wejściowa to ( x , k ) z parametrem k , p jest wielomianem, a f jest funkcją obliczalną .f(k).p(|x|),f(k).p(|x|),f(k).p(|x|),(x,k)(x,k)(x,k)kkkpppfff Możliwe jest zastąpienie wymogu...
Mam pytanie dotyczące redukowalności SERF impagliazzo, Paturi i Zane'a oraz algorytmów podwykładniczych. Definicja SERF-redukowalności daje następujące: Jeśli jest redukowalne przez SERF do P 2 i istnieje algorytm O ( 2 ε n ) dla P 2 dla każdego ε > 0 , wówczas istnieje algorytm O ( 2 ε n )...
Raz za Parallel twierdzenie pretition to ważny wynik w PCP, inapproximation, itd. Twierdzenie jest fomalized następująco. Gra , gdzie S , T , A , B są zestawami skończonymi, π jest rozkładem na S × T i predykatem V : S × T × A × B → { 0 , 1 } . Określ wartość gry v ( G ) = max hG = ( S, T, A, B,...
Czy istnieje dowód, że emulacji maszyny Turinga na nieświadomej maszynie Turinga nie można wykonać w mniej niż gdzie jest liczbą kroków, które wykonuje maszyna Turinga ? Czy to tylko górna granica?O ( m logm )O(mlogm)\mathcal{O}\left(m\log m\right)mmm W artykule Paula Vitányi o relatywizowanych,...
Chciałbym wiedzieć o historii tych dwóch terminów: „ skuteczny ”, „ wykonalny ”. Kto zastosował je po raz pierwszy w obliczeniach / algorytmach? (w nowoczesnym znaczeniu tych terminów, tj. XX wieku). Jak stały się głównym nurtem? Jak te dwa terminy zaczęły być używane jako synonimy? Wiem, że...
Czy wiadomo, czy problem z ustawieniem wierzchołka sprzężenia zwrotnego na niekierowanych grafach płaskich o ograniczonym stopniu jest
Czy ktoś może wymienić niektóre dobrze znane problemy, które spełniają następujące warunki: 1. has a generalization problem that is known to be NP-complete 2. has not been proved to be NP-complete nor has a known polynomial time solution.
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...
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 )....
Wydaje mi się, że eksperci od uczenia maszynowego / eksploracji danych znają P i NP, ale rzadko mówią o niektórych bardziej subtelnych klasach złożoności (np. NC, BPP lub IP) i ich implikacjach dla skutecznego analizowania danych. Czy jest jakaś ankieta na temat tej
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 →...
Łatwo zauważyć, że jeśli to istnieją całkowite N P problemy wyszukiwania, których nie można rozwiązać w czasie wielomianowym (stwórz całkowity problem wyszukiwania, mając zarówno świadków członkostwa, jak i świadków braku członkostwa).N P ∩ c o N P ≠ PNP∩coNP≠P\mathsf{NP}\cap\mathsf{coNP} \neq...
Problem podziału jest słabo NP-zupełny, ponieważ ma wielomianowy (pseudo-wielomianowy) algorytm czasowy, jeśli wejściowe liczby całkowite są ograniczone przez jakiś wielomian. Jednak 3-partycja jest silnym problemem NP-zupełnym, nawet jeśli wejściowe liczby całkowite są ograniczone przez...
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ę...
Biorąc pod uwagę macierzy A z racjonalnym pozycji. Jaką złożoność sprawdzenia A można diagonalizować?n×nn×nn\times nAAAAAA Podejrzewam, że można to zrobić w P, ale nie znam żadnego odniesienia. Bardziej interesujące jest jednak pytanie, czy istnieje jakaś lepsza klasa złożoności, aby uchwycić ten...