Teoretyczne informatyka phase-transition

12

Sparametryzowana złożoność od P do NP-twardego iz powrotem

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 …

60 cc.complexity-theory np-hardness big-list phase-transition

3

Czy były jakieś badania nad SAT powyżej progu satysfakcji?

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 problemów z wystarczająco małym ,m n …

25 cc.complexity-theory sat random-k-sat phase-transition

4

Przykłady przejść fazowych twardości

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 prawidłowe ważone kolory, niezależne …

20 cc.complexity-theory counting-complexity approximation-hardness phase-transition

3

Jak często występuje przejście fazowe w problemach z NP-zupełnym?

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. Język wykazuje przejście fazowe (w odniesieniu do powstrzymywania), jeśliLLL Istnieje …

17 cc.complexity-theory phase-transition

1

Random 3-SAT: Jaki jest eksperymentalny zakres progowy?

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 trzeciego dowodzą , że …

14 sat phase-transition random-k-sat

2

Jaka jest dokładna definicja Random K-SAT?

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 …

12 cc.complexity-theory sat randomness phase-transition

1

Co wiemy na temat przejścia fazowego problemów # P-Complete?

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ż wiedzieć, czy istnieje takie zjawisko w przypadku …

11 cc.complexity-theory counting-complexity phase-transition

1

Jakie są obecnie najbardziej znane górne i dolne granice progu (nie) satysfakcji dla losowego k-sat i / lub 3-sat?

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 granic.

10 cc.complexity-theory sat lower-bounds upper-bounds phase-transition

Pytania otagowane jako phase-transition