Szukam przykładów problemów sparametryzowanych liczbą , gdzie twardość problemu nie jest monotoniczna w k . Z mojego doświadczenia wynika, że większość problemów ma przejście jednofazowe, na przykład k- SAT ma przejście jednofazowe od k ∈ { 1 , 2 } (gdzie problem występuje w P) do k ≥ 3 (gdzie...
Dobrze znaną cechą instancji SAT jest stosunek liczby klauzul do liczby zmiennych , tj. Iloraz . Dla każdego istnieje wartość progowa st \ dla , większość instancji jest zadowalająca, a dla większość instancji jest niezadowalająca. Przeprowadzono wiele badań dotyczących problemów, w których , oraz...
Załóżmy, że mamy problem sparametryzowany parametrem p o wartości rzeczywistej, który jest „łatwy” do rozwiązania, gdy i „twardy”, gdy p = p 1 dla niektórych wartości p 0 , p 1 .p = p0p=p0p=p_0p = p1p=p1p=p_1p0p0p_0p1p1p_1 Jednym z przykładów jest liczenie konfiguracji spinów na wykresach. Licząc...
Powszechnie wiadomo, że wiele problemów z kompletnym NP wykazuje przejście fazowe. Interesuje mnie przejście fazowe w odniesieniu do ograniczenia w języku, a nie twardości danych wejściowych w stosunku do algorytmu. Aby pojęcie było jednoznaczne, formalnie zdefiniujmy go w następujący sposób....
Krytyczny stosunek klauzul do zmiennych dla losowej 3-SAT jest większy niż 3 i mniejszy niż 6, i wydaje się być powszechnie opisywany jako „około 4,2” lub „około 4,25”. Mezard, Parisi i Zecchina udowadniają (w sensie fizyki), że współczynnik krytyczny wynosi 4,256, podczas gdy autorzy pierwszego i...
Istnieją 4 różne ograniczenia, które możemy mieć, definiując Losowy K-SAT. 1) Całkowita liczba literałów w danych klauzulach to dokładnie K lub AT, w większości K 2) Dany literał może być używany z lub bez zamiany w tej samej klauzuli (A lub A lub A) 3) Daną zmienną można użyć z lub bez zamiany w...
Co wiadomo na temat przejścia fazowego w problemach # P-Complete? W szczególności, czy istnieje inne przejście fazowe dla # DNF-k-SAT i # CNF-k-SAT? Aktualizacja: Jak wiemy, w Random k-SAT występuje przejście fazowe, w którym rozwiązanie problemu staje się łatwe i trudne. Chciałbym również...
Chciałbym poznać aktualny stan przejścia fazowego dla losowego k-sat, biorąc pod uwagę n zmiennych i klauzul m, co jest najlepiej znanym c = m / n dla górnych i dolnych