Preambuła Interaktywne systemy dowodowe i protokoły Arthura-Merlina zostały wprowadzone przez Goldwassera, Micali i Rackoffa i Babai w 1985 roku. Początkowo sądzono, że ten pierwszy jest potężniejszy od drugiego, ale Goldwasser i Sipser wykazali, że mają taką samą moc ( w odniesieniu do...
Jestem ciekawy w szerokim znaczeniu tego, co wiadomo na temat algorytmów równoległych w P. Znalazłem następujący artykuł w Wikipedii na ten temat: http://en.wikipedia.org/wiki/NC_%28complexity%29 Artykuł zawiera następujące zdanie: Nie wiadomo, czy NC = P, ale większość badaczy podejrzewa, że...
Jaki jest związek między algorytmami DNA a klasami złożoności określonymi za pomocą maszyn Turinga? Czym są pomiary złożoności, takie jak czas i przestrzeń w algorytmach DNA? Czy można je wykorzystać do rozwiązania problemów związanych z NP-zupełnymi, takich jak TSP, których maszyny von Neumann nie...
1- Czy są jakieś szczególne właściwości macierzy przylegania, gdy wykres jest płaski? 2- Czy jest coś specjalnego do obliczania stałej macierzy przylegania, gdy wykres jest
(crossposted z MathOverflow) Cześć, Czytałem ten wątek: /mathpro/16393/finding-a-cycle-of-fixed-length Chcę znaleźć 5-cykl na wykresie. Tak naprawdę to, czego naprawdę chcę, to najkrótszy nieparzysty cykl o długości co najmniej 5, ale może to trochę poza tym. Dla moich celów, traktuję i to samo...
Rozważ zestaw płaskich wykresów, w których wszystkie ściany wewnętrzne są trójkątami. Jeśli jest punkt wewnętrzny nieparzystego stopnia, wykres nie może być trójkolorowy. Jeśli każdy punkt wewnętrzny ma równy stopień, czy zawsze może być trójkolorowy? Idealnie chciałbym mały...
(Jest to kontynuacja tego pytania i odpowiedzi ). Mam następujący całkowicie nieimodularny (TU) całkowity program liniowy (ILP). Tutaj są dodatnimi liczbami całkowitymi podanymi jako część danych wejściowych. Określony podzbiór zmiennych x i j jest ustawiony na zero, a reszta może przyjmować...
Widziałem (i słyszałem), że twierdził, że można bezpiecznie dodać klasyczny aksjomat wykluczonego środka do Coq, ale nie mogę znaleźć dokumentu potwierdzającego to twierdzenie. Artykuły, które widzę na liście na wiki Coq o wykluczonym środku, wykazują niespójność z impredykatywnym...
Kod Huffmana dla rozkładu prawdopodobieństwa jest kodem prefiksu o minimalnej średniej ważonej długości słowa kodowego , gdzie jest długością tego słowa kluczowego. Jest dobrze znanym twierdzeniem, że średnia długość na symbol kodu Huffmana zawiera się między a , gdzie jest entropią Shannona...
rejestruje ideę skutecznie parallelizable i jeden interpretacja jest to, że problem można rozwiązać w czasie O ( log C n ) za pomocą O ( n k ) równoległych procesorów dla niektórych stałych c , k . Moje pytanie brzmi, czy istnieje analogiczna klasa złożoności, w której czas wynosi n c, a liczba...
Lemat o pompowaniu dla języków regularnych może być udowodnione przez rozważa automat skończony, który rozpoznaje stan języka badanego, zbierając ciąg o długości większej niż jego liczby stanów i stosując zasadę zaszufladkować. Jednak pompowanie lematu dla języków bezkontekstowych (a także lematu...
To pytanie jest inspirowane wielomianową hipotezą Hirscha (PHC). Biorąc pod uwagę -facet polytop w , czy szczelina widmowa jego wykresu wierzchołek-krawędź (nazwij to ) jest niższa ograniczona przez ? Zauważ, że wykres cyklu wierzchołków pokazuje, że nawet dla szczelina widmowa może być tak mała...
Zainspirowany tym pytaniem jest faktoring znany jako P-hard , zastanawiam się, jaki jest obecny podobny stan wiedzy na temat twardości izomorfizmu grafów. Jestem pewien, że obecnie nie wiadomo, czy GI jest w P, ale: jaka jest obecnie największa klasa, w której GI jest trudniejsza? (nie było...
Luca Trevisan pokazał, ile konstrukcji generatorów pseudolosowych można uznać za konstrukcje ekstraktorów: http://www.cs.berkeley.edu/~luca/pubs/extractor-full.pdf Czy istnieje sensowna rozmowa? Tj. Czy „naturalne” konstrukcje ekstraktorów można traktować jako konstrukcje pseudolosowych...
Czy istnieje jakakolwiek prawdopodobna hipoteza złożoności / kryptografii, która wyklucza możliwość, że obwody wielomianowe mają rozmiar podwykładniczy (tj. z ) ograniczoną głębokością ( ) obwody? ϵ<1d=O(1)2)O ( nϵ)2O(nϵ)2^{O(n^\epsilon)}ϵ <
Ostatnio zacząłem szukać algorytmów aproksymacyjnych dla problemów trudnych dla NP i zastanawiałem się nad teoretycznymi przyczynami ich badania. (To pytanie nie ma być zapalne - jestem po prostu ciekawy). Z badań algorytmów aproksymacyjnych wynikła pewna naprawdę piękna teoria - związek między...
Ostatnio pracowałem nad problemem obliczania przybliżonej sumy listy posortowanych liczb nieujemnych. Dla każdego ustalonego opracowano schemat aproksymacji czasu , który daje przybliżenie dla sumy. Artykuł opublikowano na stronie http://arxiv.org/abs/1112.0520 , który nie został jeszcze...
Może ktoś będzie w stanie wyjaśnić różnicę między: Algebraiczne typy danych (które dość dobrze znam) Uogólnione algebraiczne typy danych (co czyni je uogólnionymi?) Rodzaje indukcyjne (np. Coq) (Szczególnie typy indukcyjne.)
Bramka AND & OR jest bramką, która ma dwa wejścia i zwraca ich AND oraz OR. Czy obwody wykonane tylko z bramki AND & OR, bez fanouta, mogą wykonywać dowolne obliczenia? Mówiąc ściślej, czy obszar logiczny obliczeń wielomianowych można zredukować do obwodów AND i OR? Moja motywacja do...
Jak wiemy, funkcja - pobiera ( obejmujący ) z pełnego wykresu -vertex , i wyprowadza iff zawiera klik . Zmienne w tym przypadku odpowiadają krawędzi z . Wiadomo (Razborov, Alon-Boppana), że dla funkcja ta wymaga obwodów monotonicznych o wielkości około . C L I Q U E ( n , k )kkkdoL IQ Umi( n , k...