Czytałem trochę o metodzie sumy kwadratów (SOS) z badania Baraka i Steurera oraz notatek z wykładu Baraka . W obu przypadkach zamiatają pod dywan dywaniki o dokładności numerycznej. Z mojego (co prawda ograniczonego) zrozumienia tej metody powinny być spełnione następujące warunki: Biorąc pod...
Czy coś wiadomo o drugim najmniejszym - t -cut w sieci przepływowej? Lub, bardziej ogólnie, na temat tego problemu:sssttt Dane wejściowe: sieć i liczba k , wszystkie w postaci binarnej. Wyjście: K k najmniejszy odcinek s - t .N.NNkkkkkksssttt -tej najmniejszej s - t cięcia ( S , T ), to...
Interesuje mnie zrozumienie struktury klasy grafów taki sposób, że na czterech wierzchołkach nie ma podgraphu indukowanego wierzchołkiem, który jest idealnym dopasowaniem. Zaznaczono inaczej, dla wszystkich czterech wierzchołkach , b , c , d , w G jeśli b i c d są krawędzie to wykres powinien...
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...
Szerokość i szerokość ścieżki są popularnymi parametrami, mierzącymi odpowiednio bliskość wykresu do drzewa lub ścieżki. Rzeczywiście wydaje się, że szerokość jest tak popularna, że pojawia się w wielu artykułach, książkach i notatkach z wykładów, które dają (nawet bardzo delikatne) wprowadzenie...
Rozważmy problem, w którym jako dane wejściowe podajemy ukierunkowany wykres acykliczny , funkcję znakowania λ od V do jakiegoś zbioru L o całkowitej kolejności < L (np. Liczby całkowite) i gdzie jesteśmy proszeni o obliczyć leksykograficznie najmniejszy rodzaj topologiczny G pod względem λ ....
Gdy chcemy udowodnić, że jest N P -Complete, to standardowe podejście jest wykazują czasie wielomianowym obliczalny wiele-jeden redukcji znanego N P -Complete problemu do L . W tym kontekście nie potrzebujemy ścisłego ograniczenia czasu działania redukcji. Wystarczy mieć dowolne wiązanie...
Zgodnie z tym artykułem , który omawia niedeterministyczne rozszerzenie hipotezy silnego czasu wykładniczego (SETH), „[…] Williams ostatnio wykazał, że podobne hipotezy dotyczące złożoności k-TAUT Merlina i Artura są fałszywe”. Jednak ten artykuł przytacza jedynie osobistą korespondencję. W jaki...
Powszechnie wiadomo, że właściwość Church-Rosser obejmuje redukcję w prostym typie rachunku lambda. Oznacza to, że rachunek różniczkowy jest spójny w tym sensie, że nie wszystkie równania obejmujące terms można wyprowadzić: na przykład K I , ponieważ nie mają one tej samej postaci normalnej.λ...
Jak trudno jest znaleźć najrzadsze rozwiązanie układu równań liniowych? Bardziej formalnie, rozważ następujący problem decyzyjny: Instancja: układ równań liniowych o współczynnikach całkowitych i liczbie ccc . Pytanie: Czy istnieje rozwiązanie dla systemu z co najmniej ccc zmiennymi przypisanymi...
Czy to prawda, że dodanie aksjomatów do CIC może mieć negatywny wpływ na zawartość obliczeniową definicji i twierdzeń? I zrozumieć, że w normalnych zachowań teoria, wszelkie zamknięte termin zostanie zredukowany do kanonicznej normalnej postaci, na przykład w przypadku jest prawdziwy, wówczas n...
Logika liniowa jest interpretowana za pomocą Spójnych przestrzeni i są one wyraźnie widoczne w artykułach Girarda. Znam wszystkie trzy główne sposoby formalnego ich zdefiniowania i tak naprawdę nie stanowią żadnego problemu w używaniu i udowadnianiu różnych rzeczy, ale po prostu nie rozumiem, co...
Szukam: Michael O. Rabin, „Stopień trudności obliczenia funkcji i częściowe uporządkowanie zbiorów rekurencyjnych”, Uniwersytet Hebrajski, Jerozolima, 1960 Streszczenie: „Próbujemy zmierzyć ilość pracy związanej z obliczeniem danej funkcji obliczeniowej (rekurencyjnej). Wprowadzono i zbadano...
Lance Fortnow stwierdził ostatnio, że udowodnienie L! = NP powinno być łatwiejsze niż udowodnienie P! = NP : Oddziel NP od przestrzeni logarytmicznej. Podałem cztery podejścia w ankiecie przeprowadzonej przed blogiem w 2001 r. Na temat diagonalizacji (sekcja 3), chociaż żadna z nich się nie...
Dla których niekierowanych wykresów są wszystkie drzewa pierwszego wyszukiwania głębokości (dla wszystkich możliwych wierzchołków początkowych i dla wszystkich wyborów, których sąsiadów najpierw szukać) ścieżki skierowane? Oznacza to, że każde drzewo DFS powinno mieć tylko jeden liść, a każdy inny...
Teraz widzimy, że Kościół był związany z tym po prostu wpisane rachunek lambda . Rzeczywiście wydaje się, że wyjaśnił on prosty typ rachunku Lambda, aby zmniejszyć nieporozumienia dotyczące rachunku Lambda. Teraz, gdy John McCarthy stworzył Lisp - oparł go na rachunku Lambda Calculus . Jest tak,...
Wiadomo, że w przypadku następnie wielomian hierarchia zapada się Ď P 2 i M A = A M .N.P.⊆ P./ PO l rNP⊆P/PolyNP\subseteq P/PolyΣP.2)Σ2P\Sigma_2^{P}M.= MMA=AMMA = AM Jakie są najsilniejsze znane upadki, jeśli ?N.miXP.⊆ P./ PO l rNEXP⊆P/PolyNEXP\subseteq
Jaki jest najszybszy znany algorytm deterministyczny, który może rozpoznawać skierowane wykresy za pomocą pary rozłącznych cykli wierzchołków? Wiem, że wykresy z min. Min. Trzech zawsze mają taką parę ( Thomassen'83 ), ale mimo to nie mogę znaleźć skutecznego algorytmu w ogólnym przypadku. Czy ktoś...
Klasa złożoności PPAD została wynaleziona przez Christosa Papadimitriou w jego przełomowym artykule z 1994 roku . Klasa ma na celu uchwycenie złożoności problemów wyszukiwania, w których istnienie rozwiązania jest gwarantowane przez „Argument parzystości w grafach ukierunkowanych”: jeśli w grafie...
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 ....